From your updated description I would do the return line overflow test. It is not all that common for two pump elements to fail close to each other. The common cause of two elements not fuelling the injectors that are at one end of the pump is either too much air introduced to the pump with the fuel or not enough fuel getting into the pump. . Both conditions can produce fuel starvation of some elements. Both weak power and other effects like rough idle and no start conditions can easily result.

It could and probably is the worn elements in your old pump of course. Nothing is written in stone or very few things are in this world.

I would want to check the pumps return output for no air output into the return line as well as enough volume of fuel to sustain proper operation of the pump. It is a very simple test and means you will not be chasing other things later.
Probably it is fine but you have to be certain in my opinion. I know the new pump seems to idle better yet if the temperature has had a real swing lately this can have an effect not really calculatable on air leaks or volume delivery of fuel to the pump. You really have many things to check out if the timing of the pump does not bring the power back.
The chances of two pumps producing low power are not high. Keep what I have mentioned in mind. Sorry to drone on. I really just want you thinking if setting the pump timing does not improve things enough. I still hope it's just really the pump timing.