Here is my stock answer to your question:
To help clarify your options, run these two tests:
a) Run your games, but lower your resolution and eye candy.
If your FPS increases, it indicates that your cpu is strong enough to drive a better graphics configuration.
If your FPS stays the same, you are likely cpu limited.
b) Limit your cpu, either by reducing the OC, or, in windows power management, limit the maximum cpu% to something like 50%.
This will simulate what a lack of cpu power will do.
Go to control panel/power options/change plan settings/change advanced power settings/processor power management/maximum processor state/
set to 50% and see how you do.
If your FPS drops significantly, it is an indicator that your cpu is the limiting factor, and a cpu upgrade is in order.
It is possible that both tests are positive, indicating that you have a well balanced system, and both cpu and gpu need to be upgraded to get better gaming FPS.
I am not certain if upgrading from a 4 core to a 6 or 8 core cpu will do the job for you.
It will be very effective if your games are multi core enabled. Few are, most can only use 2-3 cores. That puts a premium more on the effectiveness of each core.
If you can overclock, you will get help there.
If you are going to upgrade your cpu, and your budget is in the FX-8350 area, consider a Intel 3570K which is perhaps 30% more effective per core, and has a high oc capability. This assumes that your problem is individual core power, not the need for added cores.
You would also need a Z77 based motherboard.
I suspect that this option is more costly than what you have in mind.