Interesting limitation. Let's see how it plays out using the same analysis.
That's... rather unexpected. From this point of view, it looks like -2/+4 is actually better than -5/+10--the max AC threshold is 3 points higher! Using the Paladin from my OP, with -2/+4 he should power attack against AC 18 or less. (At level 4, that's practically everybody.) But that doesn't tell the whole story, because we still have to see which version grants more DPR. Comparing -2/+4 to -5/+10, again using the 4th level Paladin from the OP, yields the following graph:
The left axis is DPR, the bottom axis is target AC, the blue line is -2/+4, and the red line is -5/+10. Per the graph, against AC 13 and below, -5/+10 is best. Against AC 14-18, -2/+4 is best. Against AC 19+, normal attacking is best. Remember, this is a calculation for the specific 4th level Paladin in the OP, who has +4 Str, a Greatsword, and the Great Weapon Fighting Style, and these numbers will be different for other characters.
In summary, it looks like -2/+4 isn't exactly a straight nerf to the feat; it just weakens it against low AC (12-13) creatures, while making it stronger against mid and high AC creatures.