Once you sign in on your phone, you can go to the Google Play site on your computer, and click on 'My Apps', then click 'Install' for each app. It's repetitive, but it goes by much quicker than trying to do it on your phone. You'll want to make sure your phone is connected to a wifi network though, otherwise it'll eat up your data.
I've had to go through the replacement phone process a couple of times, and found this method to be the quickest. If it were running ICS, it'd automatically re-install all the apps itself.