NO, I think SSD first, all other options second, IF there is not a thermal problem.
Let's be clear though. Just because you don't "FEEL" any heat, does not mean ANYTHING, at all. INSIDE the CPU, the cores can go to to over 100°C and back down to 50 or 60°C in MILLISECONDS. OR, they can stay above throttle temp for seconds or minutes at a time, while under a working load, and you would have no idea, especially if the fan is not responding properly. Have you noticed ANY change in fan behavior, as in, running fast more often or all the time, or not hearing high speed fan operation AT ALL?
Without actually running a monitoring utility, you can't have ANY idea what kind of temperatures your processor is actually running at AND what you "think" makes very little difference when it comes to what's actually going on. It might not be getting hot, but knowing for sure would make a hell of a lot more sense than just "thinking" it's not. Then you could move on to these other solutions knowing that you aren't ignoring a very basic problem because you were sure it was not getting hot when it fact it was.
This is not just some guess I pulled out of my #$%. This is a very common problem on laptops, especially on models that have high core counts because they tend to run a lot hotter which is exactly why MOST previous generation i5's and i7's did not have the same amount of cores on the mobile versions as they did on the desktop versions. They simply could not control the heat under a load, so using fewer cores was always the answer. There is only so much room for cooling inside a laptop, unlike a desktop, so options are limited when it comes to finding a balance between performance and managing the thermal ceiling.
You lose nothing by just verifying that temperatures are good/ok. You might lose everything by ignoring the idea that there could be a thermal issue, especially if you are in the middle east somewhere where ambient temperatures run MUCH higher than in other regions. If that is the case, you are already starting out far closer to the maximum temperature that the device can withstand than another user from say, Canada, or Russia, or even more northern areas of the US where the average ambient temperature is much cooler.
So my advice would be to replace that HDD with an SSD, but also take the time to check and see that there are not any thermal issues. Don't guess. KNOW.