Is the migration as easy as installing the paid key and removing the free key from the key bank?
Exactly. You don't need to re-install anything. Just delete the free key from the License Key Storage and install the commercial key instead. This will make your address book capable to hold an infinite number of records.
Can I do all this remotely (a few of the remote hosts are physically a few hundred miles away)?
Remote Hosts have nothing to do with the registration process. It happens on the Viewer side only. Provided that you use version 6.x of course.