To improve cooling in your computer case, you could take the CPU cooler out, the memory sticks, the graphics card and the PSU, and get everything dusted out. Use a compressed air can and the dust will come out, trust me on that!
Also, I own a HP computer and I know how messy the cables can be, I even dismounted every piece of my PC and mounted it back on, while managing the wiring as well, the result is a much better ventilated and dust free computer, no rat nests!
When reapplying thermal paste, get rid of what's already on the GPU, watch some youtube videos about how to apply thermal paste and do it!