I’d suggest giving the paste a year or two. Most thermal pastes have a life of around 3-5 years, depending on the heat they’re dealing with.
Most laptops have the heatsinks facing the bottom, so replacement is easier. And if it’s on the other side (like Apple devices; ugh) then it’s a !&&* of a time replacing it. Just be careful, don’t take risks, and you should be fine!
Good luck!