Paladin Leveling

Which is the best spec to leveling a paladin ? i imagine it being holy and just spamming dungeons (if the xp boos applies in dungeons) but i really dont know answers are apprciated :)

If your strategy of leveling is throwing all of the quests into a garbage can and just spamming RDFs, then yes, with holy you will get faster queues. However, that is one of the worst leveling strategies ever. Quests should be your main priority, especially at later levels - it will give you way more experience much faster.

I have leveled my paladin as a retribution and I can say that it's fairly easy, though until level 40 you won't have a lot of abilities to kill enemies with. Prot might even be better since you will take less damage from opponents, have way faster RDF queues (do both quests AND dungeons) and have easier time dealing with several mobs simultaneously.

I'd go as prot, faster RDF queue if you're into that, but killing 3-4 mobs at a time is not an issue. I don't think I've died more than 4-5 times while leveling my paladin in prot spec, damage was sometimes lacking if you need to kill one of those badass creatures, but you can solo them, unlike ret spec probably.
Spamming dungeons worked really well for me as I was lazy, playing on the other account while my leveling char got a queue up, but I would not recommend it as it's not the fastest way. You can do quests while in the queue so you take a break from the horrible quests like "kill 8 of these, 10 of those and bring 14 of that."

Either Retribution or Protection for leveling..Both will be a slight pain until you get Crusader Strike or Avenger's Shield but after that its a breeze.

Holy is unfit for leveling as you will have low damage and mana issues. Protection seems nice on first look, but it only really becomes good after you get Divine Plea, which happens at 72lvl. Before that it's the same as Holy - low damage and mana issues. The argument that Prot gets you faster in RDF is irrelevant because you can also tank as Retri in the same gear, as long as you have a 1h+shield in your bags. Retri has the highest damage, it has no mana issues after getting the judgement talent at around 40lvl, and it also has decent sustain through the instant flash heals.

tl;dr - go Retri, don't fall into the trap thinking that Prot is somehow better (at least until Divine Plea)

In my experience prot hits like a beast in dungeons, especially on lower lvl.
When u tank +3 mobs a prot pala usually out DPS the dmg dealer of the party.
Funnily enough the only class that is able to deal more DPS in dungeons is prot warr due to revenge.

In theory prot should be able to deal more DPS than ret while solo questing by attacking multiple mobs at once.
The main issue is though that prot runs faster oom so I would recommend ret for solo questing.