Yes, sounds like heat. It can be the CPU, the GPU, the PSU or the case. Many modern cases have the PSU air intake with a dust filter facing down towards the floor and the feet of the case usually aren't too tall. Hand on heart, how many of you ever check the dust filter under your case? And how many have a thick carpet under the computer? Checking the inside dust is easy especially in a windowed case but the bottom rarely gets any attention.
Another place to check for dust is the front of the case. Again, depending on the model, there may be a detachable dust filter behind the front panel. Some cases may require removing the front panel for de-dusting.
Yet another thing to check is the seating of fans and cooler blocks. Especially the Intel type plastic prongs can be tricky to fasten properly and when enough time passes they can get just a tad loose at one corner. Obviously that will drastically weaken the contact between the cooler and the CPU, causing heat related issues. Mine worked fine for several years until at one meeting my computer wouldn't start. I've also seen the heat paste having drained halfway off the top of the CPU!
Apart from Windows Update, the Store requires updating the apps every once in a while. That won't explain such a drop in FPS, though.
