I think DA is better for PvP because of his offensive skills. I have never played a Paladin but as I look to his skills I think he is more for PvE because of his defensive skills.
I have no idea on how these two classes will do in catacombs...sry
DA is going to be better for pvp, you have your cat, which at higher levels can do some uber damage, p atk is outrageous. If leveling in catacombs, for the most part, Pally would be better, they have Sacred attacks, MOST things in a cata or necro are demonic and weak against sacred attacks.