While you're putting together your iron filings order - a single KG should do:
Have you got any isopropyl alcohol? - isopropyl wipes will do if you haven't. This will be needed to clean off the, probably, solid thermal paste off your CPU. I'm presuming it's solid as your temps were really high - that or there's very little/uneven fit.
You can buy dedicated
TIM cleaner but it's stupidly expensive for the amount you get - but easy to purchase with the cooler and you'll probably still not use it all, ever. Alternatively you can use methylated spirits (90% ethanol/isopropyl 10% methanol) if you have any in your garage, but be sure to wipe off any residue that may be left and it will take longer to evaporate - and you will need to take more care if using this. But ideally pick up some isopropyl/wipes.
I'll talk you through the cleaning process but have links too that should help. It's very easy with IP and using paper towel/coffee filters - if it's really dry/hard you sometimes have to dab the IP onto it with paper towel to soften it before it can be wiped off (not sodden paper towel). When it's all off you wipe the top of the CPU until it's spangly clean and shiny with the IP. The IP evaporates almost immediately (you dab it onto the paper towel) and will leave the CPU looking as good as new when finished polishing.
You will probably need to remove the motherboard - it will certainly make it easier to remove and fix the cooler - depends on the access you have to the back plate.
Personally, I would take the opportunity to remove the motherboard - and give the inside good spring clean. Wipe down case fans with a paint brush and hoover all the debris from your filters and dust from the base if your case etc..
You will also find it infinitely easier to remove and fit your new cooler - which i'm happy to walk you through (will need an approximate time).
Take photos of your cables etc before you start/remove - this will give you a visual aid and give you a reference when inserting your cables back. Ideally, out your SATA leads back in the same ports so Windows doesn't reassign different letters etc.