My laptop has a cooling issue

For the past year or so my laptop has developed a cooling issue. It gets very hot and the fan is noisy. This is more noticeable when running Windows than Linux (it's a dual boot) and when running demaning software, but that's obvious I guess. I recently changed the harddrive and tried to clean it when I had already opened it up, but I found it hard to actually access the CPU, which I imagine is what is causing the problem. The hot spot is mainly the bottom left corner, under my left hand. I've been considering opening it up again and see if I can clean it again, but it really didn't have much effect. I've also thought about cooling paste, but since I couldn't really figure out how to access the CPU that seems difficult. Google has not been helpful so far.