You might try full synthetic oil, it holds pressure better when it is warmed up. It will allow starts in colder weather that petroleum oils will not, even in the same grade. You could go to a heavier weight in the synthetic too and still be able to start in cold weather.
I would say that you are correct, there is enough wear in the engine to cause the symptoms you describe but it will be everything, not just the pump or just the bearings. The lifters and valve gear as well as the cam bearings are unlikely to be trouble, the main leaks will be at the crank and pump. You can replace all those bearings without pulling the engine, all from below. Of course, the easiest thing to do would be to change the pump and see what you get. I would guess you will need to change the bearings too if the oil change does not help
