Well, I'm at 4.4Ghz and don't break 57C with prime and that's a similar setup you have. The 2600k and 2500k are very similar. So let's do the run down.
First, Thermal Paste application.... MAKE SURE YOU DO IT RIGHT! There's plenty of methods for the Hyper 212 but my favorite is prefilling the small gaps between the heat pipes and mounting block and flattening with a credit card. After that I prefer doing the 2 grains of rice in the center method. But before you just slap it together, try it once and pull it off. See if the paste covered the CPU without spilling over. Once you get a good spread (90-95% coverage), clean it off again and mount it with the same method. Don't forget to clean with a coffee filter/lint-free rag and Isopropyl alcohol 70% or higher.
During your overclock did you set the voltage on the CPU to a fixed voltage or did you leave it on auto? If you left it on Auto it may be ramping your voltage up severely. Check your voltages with your motherboards application, CPUID Hardware Monitor, CPU-Z, etc... At 4.0Ghz I can hold my 2600k steady at 1.150v and be perfectly stable. On auto my voltage will ramp over 1.3v and the temperatures jump 20C higher easily.
Last but not least in any respect. Make absolutely sure you're getting good heat extraction near the processor. The good thing about a Hyper212 is you can mount it to point straight to the rear exhaust fan. As long as you have a fan there pulling the heat off that the 212 is pushing; this isn't a worry.
Let me know if this helps you solve the problem as your temps are very high for a 2500k topped with a 212 at only 4Ghz.
I can hold 4.6Ghz at that voltage LOL Try setting it to fixed in the BIOS to 1.2v and see if you are stable. I can actually boot at 1.100v at 4Ghz so 1.2v should be 100% stable and it should hypothetically drop your temperatures greatly. If you are wanting to keep the automatic "rising and lowering" voltages I can explain a bit about setting a voltage offset. The downside to having fixed voltage is that your processor is ALWAYS getting the selected voltage and it disables Speedstep. Speedstep allows the processor to actually drop the multiplier during idle. My current setup is at 4.4Ghz and I drop to 1600mhz when I'm at an idle like right now with just browsing. Also my voltage goes to about 1.275 at max load while right now idling is around 0.950v.
Try setting a fixed voltage of 1.125 and the clock to stock at 33x multiplier. Run prime then and see what the temperatures are. If they go over 60C or so, I'd be preparing to rip that 212 off. Those settings I don't even hit 55C on IntelBurnTest. And IntelBurnTest gets my CPU about 8C higher than Prime ever has.
Oh I almost forget. Make sure you set your fan speeds in the BIOS. If the fan is at an idle while the processor is running PRime at 65C, it's just going to keep heating up.
That's fine, give it ten minutes or so to max out and see. Make sure your CPU fan is set to speed before it gets hot. I would go with 40C = 100% that way it's cooling effectively.
See what happens there and if it still rolls over 60C after 10 minutes of prime you might need to reapply. 1.15v is LOW and at stock speed you should almost be able to run the fan idle on the 212 and run prime without breaking 70C.
I re-applied the thermal paste anyway with the "pea-method". Hope it's fine now, but regarding the CPU fan..
My mobo (p8z77-v) tells me that there is a cpu fan error at the boot screen. The fan is working, but it gives me that error. I've slotted the fan into the CPU-fan slot at the top of my mobo, so don't know why that's happening.
There you go brother! See, I figured the paste was a a bad batch. We all have done it once or twice. I bet I've put 100 HSF's on to processor in the last five years and I can admit I've had a few failed attempts. Now get that processor tweaked out!
Let this sentence remind you every time though. Trust me it will help you in the future one day when you look back and remember our little thread here.
"I'm 95% sure that I applied the thermal paste correctly. I've done it a few times before and it's always been fine. I spread the paste equally "
95% isn't 100% and when you need that 5%, it's not there.
As for that fan error, I'm confused.. Have you tried switching to a different header? If you're unlucky and can't boot without a fan on the header just plug an ol` case fan into it and boot with the fan into a different header.
See? I'm happy you got it bro! Those are really decent temperatures and a 4.5Ghz overclock to boot. Only thing I don't like is that 1.320v but that may just be me. I don't like taking my chip over 1.3v often and don't really have to unless I go beyond 4.5Ghz.
Either way, impressive my friend, very impressive.