I think some combination of a coolant flush, new radiator cap, and new thermostat will likely fix this. One thing I do to check the t-stat on my car if I suspect it is not working is to observe how much coolant is flowing through the top radiator hose. When the engine coolant gets hot enough, the t-stat opens, and quite a bit of coolant should be flowing through the radiator. If it’s skimpy flow, then the t-stat is probably stuck.
The other likely possibility is that the water pump is failing.