4ghz isn't really that high for the 2500k. You can get away with doing 4ghz on the stock cooler.
Personally, I'm not comfortablle with doing any overclocking with the stock cooler. I'll agree with whoever says the Cooler Hyper 212+ or EVO is a good pick for a lower overclock.
Don't junk the stock cooler. You will need it if you ever have to RMA the chip back to Intel.