ArchAngel, I took record of every single PA attack in my first two encounters for the day, here are the results:
1 - smilodon, not charging, with a lot of debuffs (-8) and no round/level buffs (like Haste). Still hits on 2+ on every attack. For low-medium AC enemies, this is always true if the companion is not debuffed.
2 - Full PA, without flanking, hits on 2+ on the last attack.
3 - Next enemy with higher AC, full PA, still hits on 2+.
4 - Next enemy, Wild Hunt Scout. Here I would miss my last attack on a roll of 6-, but it's only because I made a mistake: simply flanking with another character (I could delay for free), I would hit on 3+. I couldn't activate Inspire Courage, because I needed Dirge. That said, even if I missed my last attack on 19-, I would still gain damage from PA: without PA, the last attack would add 71 average damage (reduced by DR, so probably 60 or 50 damage), while PA already added on the other attacks a total of 75 damage (that don't care about DR). Then, again, simply remembering to flank, I am missing the last iterative only on a 2-.
5 - Attack of Opportunity: 15 free damage (30, since it's a critical, but that's not the point). Then, again, even always missing the last iterative we are gaining damage.
6 - Here I would miss on a 4-, but it's another mistake of mine: once again I forgot to flank, but I could also activate Inspire Courage to... drumroll... hit on a 2+.
7 - Here I'm moving (and in this game you move a lot): when you move, PA is free damage (well, until now it always was free damage).
8 - Another AoO: with Outflank/Combat Reflexes and a companion with 9 attacks, 7 of which crit on 15 (the last two are bites and the build could be improved adding trip for even more AoO), I'm getting one or two AoO every other round (when I'm not getting them it's only because the enemy dies before the crit). There's also the Kineticist trip.
9 - Ranged attack in melee: another AoO.
So, in conclusion, if I'm not missing something, on the Paladin PA gained 360 damage and, without mistakes, all the attacks could have missed only on a natural 1.
I stopped there because it's a tiresome endeavor, but this remained true through the entire dungeon. And it's been like that since chapter 3. I play with the TB mod too and I'm obsessed about dice rolls.