Could I use the same registration keys to install Photostory Deluxe on my new PC? Or, how could I transfer my registration key to a new installation of application on my new PC?
Yes, you can use the same registration/serial keys for the new installation as you used for the old.
However, in order to avoid any potential problems and assuming you are not going to use the program on your old computer again, with the app open on the old computer, go to Help>Deactivate program... and follow the instructions there.
If you do want to keep both installations working but find you cannot register/activate the app on your new computer, you will need to go to your Magix account, log in, go to My Products, find the listing for PhotoStory Deluxe and deactivate one of the listed activations. (You are allowed a maximum of two simultaneous activations so, of it was previously installed on another computer, you will need to deactivate that installation and licence.)