Since your not sure if you want to heal, dps, or tank, I would level the paladin to 30ish and play all three specs in dungeons starting at level 15. Healing and tanking will be easy on the low level dungeons don’t be afraid. Google the popular “Icy Veins class guides”. and use the rotations and talents so you don’t form bad habits early. There are also you tube guides on every class/spec. Almost everyone plays multiple specs on their character so keep that in mind.
If your tanking, say “new player” at the start of the dungeon so they know why your slow. go through quickly people like fast runs and almost everyone has done those dungeons many times on alts. Push the pace and only slow down if you wipe. Some dps will run ahead of you and pull if your too slow.
I think it’s a good idea to level a few classes to 25-30. For dps, havoc demon hunter is the easiest. Bm hunter, frost DK. arcane mage, ret paladin, affliction lock (maybe) are on the easy end. That said, all classes and specs are easy after you play them awhile. Don’t use a boost without testing on a level 110 trial characters and never boost a demon hunter.
Here are some threads from the past few months to browse for dps classes and other information.