Short answer: ⌘ Cmd↩ Enter works too.
Long answer: There's a second set of keyboard shortcuts that works when the focus is in the Find toolbar's input (i.e. the text box that has focus when you show the Find toolbar).
↩ Enter : Find the next occurrence of the phrase (same as ⌘ CmdG)
⇧ Shift↩ Enter : Find the previous occurrence of the phrase (same as ⌘ Cmd⇧ ShiftG)
⌘ Cmd↩ Enter : Toggle Highlight all occurrences of the phrase (same as ⌅ CtrlA)
Source: testing all key combinations I could think of, in Firefox 25 Aurora (might not work in previous versions; the Find toolbar was redesigned in Firefox 25, so some shortcuts may have changed or been added.)