On a budget, the Intel Pentium G4560 paired with a B250 motherboard would be a good choice. This is the cheapest upgrade, but also the smallest one. The next step up is an AMD B350 or A320 board with a Ryzen 1400 - B350 adds cost, but also allows overclocking. The next up would be a Ryzen 1600 with either A320 or B350. Next would be an Intel i7 with B250, and best of all is an i7-K with Z270.
Be aware that any new CPU will use DDR4 instead of DDR3 RAM, so you're not too far from a complete rebuild.