This should be another easy win.

Put Curse of Tongues on the Paladin. DPS the Warrior as much as possible. Use a Rank 1 Earth Shock -> Spell Lock -> Rank 1 ES rotation to force the first bubble. (The Warrior will be dying very fast in the space of ~15 seconds with no heals against magic.) After the bubble, Bloodlust, do the same rotation. Add in a Warstomp on the Paladin if you're a Tauren and its needed. You can easily burst a Warrior down from 50% to 0% (with a Chain Lightning/ES/Nature Swiftness Lightning Bolt combo, along with your Warlock's Shadowbolt/Deathcoil.) If they start playing defensively, go for a drain approach.

Mitigate the Warrior's damage as much as possible. CoEx/Purge Blessing of Freedom/Rank 1 FS kiting, or CoW. Its up to your playstyle. Drain the Paladin. Kill the Warrior when the Paladin is OOM.

Obvious tips:

• Purge Divine Favour, BoF, Divine Illumination.
• Warlock Perspective: Don't have auto-devour on ever vs. Paladins unless he's with a magic-debuffing partner. Your Shaman can Purge. Save it for their Hammer - against Paladin/Warrior, Paladin/Rogue, it's pretty much the only debuff you'll get that's magic (very little reason for them to put any judgements on you either of you), and it's a big deal to remove. 6 seconds is a long time for a Warrior to have free reign pounding on you.