One of the primary purposes for this is to be able to say "We (as a company) have absolutely no way of decrypting your communications", so that's a no-go. It needs to be device-to-device, or encrypted with the private key of a device, etc.
Well, in that case, we have established that both devices must be able to communicate with each other, bidirectionally and in real time, in order to complete the transfer.
In that case, there is really no need for elaborate public-key encryption schemes. In fact, they are more likely to introduce problems.
We also know that lots of people aren't really prepared to physically destroy media, have the capability to do so securely, or even understand why it might be important to do so. Instead, most people tend to just delete the file through the OS, leaving all of the data intact on the media for anyone who comes around to look. So M'vy's suggestion of letting the user copy the key onto media they have physical control over, while good in theory, isn't really a great idea in practice.
Instead, use a key exchange algorithm such as Diffie-Hellman Key Exchange (Wikipedia, RFC 2631) to allow the two devices involved to interactively agree on a shared secret. Since we don't want to reinvent the wheel, use whatever TLS or perhaps SSH/SFTP/SCP libraries are available for your target platform to do the heavy lifting. (Generally speaking, never write crypto code yourself. Odds are great that you will get it wrong, introduce subtle bugs, and leave your users' data at risk of exposure. Let someone else make those mistakes.)
Although unrelated to the cryptography itself, make sure this process involves the user authenticating on both devices in some manner.
Once the two devices have agreed on a shared secret consisting of, say, 32 random bytes, use that shared secret as a symmetric encryption key. AES-256 is good enough for most purposes these days, the 256-bit key having the added benefit of providing a safety margin also in a post-quantum cryptography world, and for a given work factor AES is not very computationally intensive.
Once you have transferred the long-term key from one device to the other and verified that the copy is good, just wipe the temporary encryption keys from both devices and possibly wipe the long-term key from the device it was transferred from (this last is likely to be your biggest problem).