I like to use the feature "Insert Phones with Users" first. I do this with their primary desk phone. That way it's just a single step and the two are associated to each other. I then follow up with Phones only if they get a second phone, making sure to reference the user account.
If you want to do them separate, do the users first. That way as you insert the phones, they can be associated to the user.