Blow out the dust bunnies and make darn sure any vents are cleared as well. Once all that is done, be certain any fans installed do work. As for cpu paste, known as thermal compound, check to see if present and/or is fully applied. Under extreme heat build-up it can splatter and exit the area it's suppose to be working on. Just re-apply and go from there. I supply a link for reapplication:
Sometimes a cleaning of dust may only move it further down the exhaust vent, so be sure it is cleared. Also, use your laptop on a hard surface. because, you're into gaming that will provide more usage and into the extreme side, no matter what you think, it just does. So, taking that into consideration if your laptop wasn't sold as a game platform, then you're pushing it. Check your laptop fan setting, if applicable it may have more active(higher RPM) to engage more quickly, etc.. You also may have an "iffy" fan that may cut out as its been too active under duress and starting to fail.