You don't need to remove the actual CPU. Turn the 4 pins on the present CPU co9oler and gently pull up on each of the 4 pins. The cooler should seperate with a bit of wiggling etc.
The CPU will have the gunk on it. Use qtips to get the gunk off, use a paper towel to clean the cpu off on the flat area, a bit of standard house isopropyl alcohol on is fine. Then use the fancy cleaning stuff for the last clean/wipedown, and put the paste on per directions.
You should remove the whole mobo for this operation, but it's up to you.