There are definitely options to use that will be strengthened from Mark of Warding's bonus to a power's defense. For the paladin in particular, it looks like you'll have to mostly rely on daily powers that lay down zones at the earlier levels and then maybe switch up to stances in the higher levels. If you hybrid, I'm positive you can find lots of pairings from utilities to at-wills. Further, seeing how you are a tiefling I believe they have a feat that allows you to take another classes utility power. So even at lower levels I'm sure you can find a feat that at the very least will be able to buff your defences up. I've included some options below, but keep in mind that this is only scratching the surface of the options available to you.
Playing a pure Paladin:
Sacred Circle lvl 2 (from phb)
Effect: The burst creates a zone that, until the end of the encounter, gives you and allies within it a +1 power bonus to AC.
Hallowed Circle lvl 5 (from phb)
Effect: the burst creates a zone of bright light. You and each ally within the zone gain a +1 power bonus to all defences until the end of encounter.
Divine Aegis lvl 16 (from Divine Power)
Effect: Until the stance ends, you and any allies with 2 squares of you gain a +2 bonus to all defenses.
Willing to hybrid?:
Cleric at-will: Priest's Shield
Hit: 1w + str modifier damage, and you and one adjacent ally gain +1 power bonus to AC until the end of your next turn.