Paladin/Warrior in 2's is about average, you won't be anywhere near as potent as Druid/Warrior but it's definitely viable.
If you find a Hunter you could do KFC, which is arguably the go-to composition for Warriors these days, but you could also grab an Enhancement Shaman and do Turbo Cleave which is not as strong as KFC, but you'll still be able to play to a high rating. There's also Kitty Cleave if you grab a Feral Druid, and If you're really feeling up to it you can grab an Unholy Death Knight and play some TSG which was pretty fun back in the day. There are probably a few other compositions you can make with other classes, but those are the ones I can name off the top of my head. Generally if you're playing with a Paladin, you'll be looking at playing as cleave (melee) compositions most of the time.
Pala/War isn't bad, most of it is just learning how to play against different comps (playing against Hunter/Priest has a lot more for you warrior to do than against say War/Pala mirror).
In 3v3 KFC is pretty straight forward along with WMP but with a non shaman healer your healer will be sitting CC a lot so Warr/ele/healer is pretty popular to offer your healer tremor/grounding/decurse.
hpala/warr is better than most of the healer/warrior comps imo. The freedoms and spammable fear plus denounce are just far too strong in 2s, plus you counter double dps 2s comps really well with bubble/bop