The first thing you should do is contact HP Support to confirm what the latest BIOS is for your laptop model and exactly what APUs the BIOS supports. That will determine what processors you can use. Next an SSD will definitely improve system performance in your laptop because the 2.5" laptop HDDs are very slow even compared to std. 3.5" desktop HDDs. Depending on how often your system needs to access the SSD to read or write data, determines how large the gains will be, but they are usually significant IME. It's worth noting that the combined performance of both the CPU/GPU will determine your gaming performance unless you add in a discrete video card - which may be the most bang for the buck. Comparing performance of the OE A8-4500M with an add-in GPU card might be useful information to determine what might work best for your purposes.
As far as the APU goes, the A8-4500M is a Trinity mobile part, and uses socket FS1r2. In my experience with HP notebooks, you will probably be able to use any of the Trinity or more recent Richmond APUs, if the notebook BIOS (UEFI) has been updated. There are only 3 APUs that you could upgrade to:
- A10-4600M Trinity
- A8-5550M Richmond
- A10-5750M Richmond
All 4 APUs are rated for 35W, so your notebook's existing cooling solution should work OK.