If the Temps you are quoting are the 4 core temps, if not look at the core temps, I use CPUID HWMonitor.
Temps are a little High, about 5 C high for the what Intel calls a HSF (stock).
The I5-2500k can go up to mid 90's at which time the CPU will start to throttle to protect them. Many say that 80 is OK, myself I do not like mine to hit 70 (Mine which is OCed to 4.6 only hits low 60's).
Just to verify. You did make sure that the four locking tabs are properly seated. Best way to check is to look at the back an insure that the white nubs are equally vivible.
On Thermal paste. Did you use the paste that came with it, or did you use artic silver 5 (Most recommended here at Tom's) If artic silver 5, then application should have been a peas sized amount spread evenly.
The Stock HSF is poorly designed and at the BOTTOM of the totom pole interms of performance. many here recommend using the Hyper 212+ (Around $30) and a great performance vs cost HSF. Myself, I do NOT even remove the Stock HSF, I always by a aftermarket HSF.
I used the paste that came with the HSF.