Upgrade CPU or GPU?

I will say upgrade the GPU if you are about the fps in a game. However, upgrading to a 1150 or 1151 socket i5 CPU would definitely help in games that are based more on CPU performance than GPU performance. If I'm not mistaken, you can get pretty close to the same OC on the 4690K as you have on the Pentium. If you do this, the CPU will just fly. However, the RX480 is a really good GPU for the money as well.

The 4690K is a SIGNIFICANT upgrade from that G3258. That would be my first move. After that I would go for the 480 8GB. Skip the little 4GB model.

The K decision comes down to the board and is $10 or 20$ extra is worth it. Do you have a Z170 motherboard? K series chips allow overclocking. my chip goes up to 4.4GHz pretty easily. If I was to go any farther I would have to make more complex overclocks instead of just a simple multiplier change. At this point I already well exceed 60FPS and usually over 100FPS in AAA titles at 1080P with all settings maxed out. I can leave vsync on without worry. With a 60Hz monitor pushing my card is worthless. Down the road I will have that luxury.

No Z170? 4690.

I use my 4690K with a 212 Evo. Usually idles right around 28-32C https://postimg.cc/image/dsl2itg4z/?_ga=1.114508487.1701167792.1480011287 during normal tasks such as movies, music, youtube or other general browsing. During gaming sessions it is usually between 42-50C. https://postimg.cc/image/3li74o6b7/ shows some numbers.

Traditionally speaking, no you can not. HOWEVER you can see here https://www.techpowerup.com/202196/asus-enables-overclocking-on-h97-h87-b85-and-h81-series-motherboards that changed with Asus. Does that also apply to the MSI board? Idk. Normally the user needs a Z97 board. How do you overclock? BCLK? Ratio? I can't say for certain which if any OC options the MSI board will offer.

Pretty much. There is a 200MHz difference.

You're welcome Maybe one day you can pass it forward.

You're welcome.

I would like to finish off that the difference between the 4690 and it's "K" version @ stock speeds is nothing. The "K" annotation just means that Intel enabled the option to change the base clock (bclk) multiplier, so you can either speed up or slow down the CPU cores to whichever you need/want.

Beware that there are two different methods of overclocking (OC'ing). Sorry, not sure how versed you are in OC'ing.
You have the bclk multiplier which is the easiest to OC and you make the largest gains here, in terms of CPU performance. In order to exploit this feature, you will need to have the "Z" version of the chipset that will match the CPU's socket. In this case, that would be Z87 or Z97 (Z97 is very much preferred, but not necessary - it is also easier to find). If you have a chipset that has a "B", "H", or another annotation, the likelihood of the mobo being able to handle any additional voltage output to the CPU would be drastically lower than if you had the "Z" version. "Z" version mobos were made to be the intended type to use with OC'ing, thus they are more robust and come with features that will help handle this more efficiently. If you don't plan on OC'ing, because the 4690(K) are super fast as is, then not having "Z" version mobo is fine.

The second type of OC'ing is bclk or Front Side BUS (FSB - older outdated term) OC'ing. This, on Intel CPUs, will be set @ 100Mhz. Upping this frequency will increase speeds of basically the whole system. This would include, the communication between the DRAM, chipset, CPU, and auxiliary components via PCI lanes (PCI-E slots). Because this speeds up the whole system, it also has many downsides. You have to consider the maximum/optimum speeds at which everything "talks" to each other and not just the CPU and its functions. Thus, most OC'ers will use this as a finishing touch to the overall OC. They will do this squeeze out every "drop" of performance they can. I personally don't do this and only use the bclk multiplier.

Sorry, I know that's a lot. If you already knew this information, then I hope someone else can at least learn from it as well. Hope, everything works out well!