No, he can't do it- but he can absolutely do something similar at 5th level. If the Paladin was 5th level and possessed the Dual Wielder feat (and thus had the extra attack feature) he could attack versatile for the second attack, because as a Sage Advice on Extra Attack said:
Extra Attack imposes no limitation on what you use for the attacks.
In the example given the Paladin doesn't have the Two Weapon Fighting Style so the only reason to use this technique would be if you had Great Weapon Fighting Style (Duelist would simply throw the axe and then swing the sword).
He can't attack versatile to start, because he's holding 2 weapons. He can attack versatile once he throws one. He took the attack action holding 2 weapons and is eligible for a bonus attack (with no damage modifier since he does not have the fighting style) with a one handed weapon- which he can make by drawing a second weapon after his attack action. Switching grips does not count as drawing a weapon, but even if we count it he is still only making his two legal weapon draws. The ability to draw 2 weapons can not be discounted in this discussion because it's integral to the feat and feats are supposed to mean big things (some arguments which were otherwise correct wanted to downplay this aspect of the feat, but that isn't quite fair). He can then make the bonus attack with either weapon (without mods) and, if the newly drawn weapon is not thrown, he can maintain his +1 AC bonus moving forward.
Note that on a versatile longsword's 1d10 with Great Weapon Fighting you're looking at a result of 3-10. If you had Duelist you could certainly throw a handaxe and attack with the versatile weapon one handed. In that instance it would be in the same range of 3-10. Admittedly, I haven't checked any other weapons (I'm pretty exclusively a sword guy).