The pairing process is a bit confusing, because it's the reverse of what most people expect. The new device generates a key, and the old device uses that key to transfer the actual credentials to the new one.
To use the pairing process, you have to start from the NEW device.
Android Phone: Settings, Preferences. Click the Connect button in the sync section
Desktop: Tools -> Set up sync -> I have an account
The new device generates a temporary key. The device must be left on the screeh with the temporary key.
On the OLD device, you go to the pair device and enter the code from the new device.
The pairing process begins - during which the Mozilla Sync server acts as a broker between the two devices to exchange the encryption key.
http://support.mozilla.org/en-US/kb/find-code-to-add-device-to-firefox-sync
You can also add devices without going through the pairing process by using your username, password, and the recovery key. http://support.mozilla.org/en-US/kb/how-do-i-set-up-firefox-sync#w_what-if-im-not-near-my-computer
(For the curious, J-PAKE http://en.wikipedia.org/wiki/Password_Authenticated_Key_Exchange_by_Juggling is used to mediate the key exchange during the pairing process, so that the sync server never actually gets a copy of the key.)
