How difficult is it to do that? I'm not very knowledgeable when it comes to hardware. Also the Hyper 212 Evo is only for the CPU, it seems like other parts of my PC are running really hot as well. Any idea what I could do with them?
Redoing the thermal paste isn't too difficult. Have a look here: Thermal Paste Removal/Installation Guide
As far as the other components go, those temps aren't absolutely terrible, but they could be better. If you have places in the case to add another fan or two, that would be my recommendation there. Otherwise, doing what you're doing now with the side off and the fan (while not the best way to go about it) will work and is basically your only other option. It just adds more dust to the situation.