Repaste again in case you got it wrong or remounted the cooler improperly.
You can often tell if you didn't quite get the paste right because temps on some of the cores are a lot higher than other cores, which is a sign that the coverage isn't very even.
If that doesn't help, new CPU cooler possibly. They're not expensive.
But to be honest, if:
- the cooler is dust free
- the cooler has fresh paste applied with decent coverage
- the CPU cooler fan is working properly
- the cooler is mounted correctly
There's no reason why temps shouldn't improve.
As for the repaste, while it might sound intimidating, it's not a particularly big deal. It's just cleaning some stuff off the CPU and the CPU cooler, both of which are flat metal surfaces. Then adding a blob of paste as per the video, and fitting the cooler again. Intel stock coolers are very easy to fit, and you're not messing around with mounting plates or any of that fun stuff.
It's stock paste on a stock cooler that's 8 years old. It's quite likely a repaste will sort the problem.