What make and model is your pc?
"The store is to replace the machine with an identical model.....which will have a different Windows 7 OEM product key"
If it is a 'big brand' factory pre-activated W7 pc - HP, Dell etc it won't have a different OEM product key. The product key on the sticker on the tower will be different but that is not the key that is used for the factory install and pre-activation.
The sticker product key is licensed to the pc maker (HP,Dell etc) and if you should ever reinstall from another DVD and have to use it then it will require telephone activation. The factory pre-activated key cannot be used for a reinstall from another DVD - it won't work as the necessary extra data will not be present on another DVD.
"backup courtesy of Paragon Hard Disk Manager 2011" is that a complete hard drive image? if so it will replace the contents of the new harddrive.
To be on the safe side - You could make an image of the 'new' hard drive so that you can go back to it should you run into problems.