On my system monitor my laptop idles at 80+ degrees celsius
EDIT: strangely enough, it has a similar temperature on high load
EDIT2: Yes I think I will order thermal paste
if you look at the CPU frequency at the high load you can see it's clocked down which is a sign of overheating. it clocks down to prevent overheating because it's unable to get sufficient cooling. you definitely have a cooling issue of some sort. it will only get slower and hotter until something breaks or it goes into thermal protection mode and shuts it self off.