Have you played Classic before?
Neither are particularly great for leveling, in my opinion, while I do like, play and have leveled both classes in Classic, warrior is by far the best tank class to play, even for leveling dungeons. Paladins can tank, but they aren’t particularly well suited for it, and though you can make it work, it will often be a team effort, requiring buy-in from your party/raid/guild, etc.
As for Prot Warrior, there is just far too much mitigation in the prot tree, and you will find yourself frustratingly rage starved without the ability to perform your role well if you choose this path for leveling.
I’d say, if you’re keep on leveling either, then go with a more dps-centric build for your warrior, and be excited about swapping between a 2 hander (most of the time) and a sword & board) when it makes sense to mitigate physical damage.
Here’s an old warrior leveling tanking guide circa 2019:
As for paladin, I’d probably look at working towards something like a 30/21/0 build for raid healing, and tanking Scholo/Strath, and DM:E jump runs.
EDIT:
Ah yeah, I kind of glazed over the solo part… As others have stated:
