I have a 2500K as well, factory clock. I'll probably look into overclocking first.
But If I were to upgrade, doesn't that mean I need to buy a new mobo first? Since the Haswell chips are LGA 1150?
Correct. Try OC first. If performance still isn't good enough, then, upgrade CPU and MB.