The M4-ATX will do the job, but it isn't needed unless you need that much power. I believe it puts out 250watts, I could be wrong, I'm just too lazy to look right now. You could power this with an M2, you would just need a 20pin ATX to 24pin ATX adapter. They're not too hard to find. One thing you need to know about HP, that 24pin connector isn't a standard ATX plug, meaning no matter which of these PSUs you decide to go with, it won't plug into the mobo. I have heard that the HP plug is just a smaller version of a 24pin ATX plug. If this holds true, all you would need to do is cut the connector off the current PSU and hardwire it into your new PSUs ATX connector. Other than that, you seem to be right on track.
I'm also a bit of a newb, but I did manage to get my first install working. That says something.

I have learned that HP/Compaq are a pain to work with. My original system was a Compaq Deskpro. That sucker had a 14 pin connector which I had to make an adapter for. I gave up and bought a standard Micro-Atx mobo. It works pretty well, except Windows98 didn't pick up some drivers and I can't seem to find them.