Asmodeus damn it, why does the enemy keep getting to roll crits?!
It's actually part of the pathfinder 2e system.
They have a system, where if you roll 10 higher than the required number it becomes a critical. I.e. If you need a 15 to hit someone, and you get a 25, then your attack becomes a critical.
On the other hand, if you get 10 under (a 5 in this situation), then you get a critical failure.
Finally, rolling a natural 20 on the die, improves you result by one stage (critical miss becomes miss become hit becomes critical hit)
And rolling a natural 1 on a dice works the other way, with the result being one worse.
It acts as a kind of level+training = minimum capability.
A dragon, who roll a d20 with a +40 will always hit a peasant with AC 10, even on a natural one.
While the peasant (+1 to hit) can still fail to hit the dragon who has Armor 40.
In this case, I would guess that the paladin was around level 5?
And we were level 2 for that fight.
So he was just going to crit us more often.