What is the correct tool/method for digging out existing concrete holes for fence posts
I doubt you can get the broken off posts out and new 4x4 posts in with the holes intact. In one case on this site the poster had clean holes and put in steel posts which are smaller enough in diameter than the original wood posts that they could be inserted plumb into the existing retaining wall. 

If your concrete is relatively weak, you might be able to break down the concrete on the two "outer" sides flanking each post using manual tools, such as a heavy steel concrete breaker bar or a heavy mattock with pick on one end.   An alternative is an electric jackhammer which you can rent.