This installment of 13th Age Options will be a little bit different. Instead of designing new feats, talents, spells, etc., I'm going to explore some possible interpretations for one of the more open-ended class talents - the Paladin's Divine Domain. Specifically, the portion that reads "if the domain you choose is designed to help Cleric spells and attacks, reinterpret the talent to help your Paladin powers." This rule exemplifies the experimental, "rulings over rules" spirit of the game as a whole, but because it shows up at character creation in might be initially intimidating for players and GMs not used to that sort of thing. The list of options I present here are by no means meant to be concrete; if you think of something that suits your Paladin better, by all means use that! But hopefully this provides a solid starting point, as well as a general overview on the utility of the different Domains for Paladins.
While you won't get as much mileage out of this domain's benefit as a Cleric (you simply don't have enough healing), it's by no means a waste. It provides a solid bonus to Lay on Hands, but it probably works best if you also have the Cleric Training talent and have chosen a healing spell. The Champion tier feat even gives you a couple uses of the Cleric's Heal spell, making this an excellent choice for a second Domain at 5th Level. The Invocation is pretty straightforward; you get a daily use of the Cleric's Heal.
You'll probably only pick up this Domain if you have a focus on healing. Either you don't have a leader-type in the party, or your leader simply focuses on buffs and action economy over healing (Bards and Commanders), so you're trying to supplement that.
This domain works perfectly fine without any reinterpretation. It's actually a really thematic domain for a Paladin, too, and a powerful party support option.
This is another domain that doesn't require any tweaking to be used by a Paladin. Most Paladins won't go for the "smart guy" concept, though, but perhaps the background points can be used to support a OUT or a backstory without using your normal allotment of backgrounds.
This strikes me as one of the more limited domains in general (you don't want your allies making death saves in the first place!), even if the base benefits work fine for a Paladin. The Epic feat notably references the Cleric's Resurrection spell, but considering it provides a free use of the spell I don't see any reason why a Paladin taking the feat shouldn't simply get a free, single use Resurrection.
This domain plays with the Icon relationship rules, and as such isn't tied specifically to Cleric abilities. Paladins, poach away! I'd also like to add that this one is a great way to add some mechanical depth to a knight in shining armor, trying to win the favor of a paramour, archetype.
The Invocation works fine for Paladins, but the base benefit modifies spells (specifically, those that can be cast for broad effect). While you could theoretically get some use out of this domain if you picked up a Cleric spell via Cleric Training, it wouldn't be worth it.
Instead, you might want to turn your Paladin abilities into broad-effect powers. For Bastion you can take half damage from attacks against up to three allies, provided you take these attacks in the same round. It's more straightforward if you're taking damage from an area attack that hit multiple targets, but that would likely be too situational. Lay On Hands might allow you to effect two or three allies with a single use, effectively turning it into a mass heal (GMs should keep in mind that a Paladin is sinking two talents into this, and talents are all that a Paladin's got, and so should be generous with the effects). For Paladin's Challenge, go ahead and have two active challenges at the same time. The Champion feat already allows this, you'll just get the benefit earlier (and for the cost of a Talent, why not?).
Some Paladins might have more than one talent that could reasonably affect additional allies. If the effect is minor, limited, or situational (Cleric Training and Paladin's Challenge come to mind here) this isn't a problem. The Bastion/Lay On Hands/Protection Domain combination, however, may need to be reigned in (allow them to affect only one additional ally each), but be sure to discuss your expectations with your player (or your GM, if you're the player).
As an alternative, generous GMs might allow a Paladin with this domain to simply pick up a Cleric spell that could be cast for broad effect, but rule that the spell only affects 2 allies (since the domain also provides an invocation, we don't want a straight-up power boost compared with a Paladin who picks up the same spell from Cleric Training; instead, we're representing what the domain would grant in addition to a base spell). Since most Clerics who benefit from this domain probably have more than just one broad effect spell, this should probably be in addition to a broad-effect Paladin talent or two. If the Paladin doesn't have any, then maybe giving them two broad-effect Cleric spells is in order.
Ultimately, each build is going to have a different combination of options that might be boosted here. My advice would be to aim low, and if the Paladin feels underwhelming give it a free broad effect Cleric spell (or two). If the player upholds the role-play aspects of the Protection/Community domain, that is. Not to the effect of being the role-play police, mind you; just be less generous with a Paladin who acts like a loner, and ask why they're really picking this domain.
Obviously the invocation works fine for Paladins, but what to do about the domain's base benefit? Paladins already wield heavy/martial weapons without penalty, so where do you go from there? Some might be tempted to give the Paladin an additional boost to weapon die size, but letting Paladins use a d12 for a big two-hander doesn't really sit right with me considering that Barbarians can't even do that.
How else might you represent better proficiency with weapons? Why, giving the Paladin access to a Fighter maneuver, of course! Since the feats are already pretty much the same idea as Smite Evil you might consider offering some alternative feats as well (though a Paladin could do worse than gaining some more pseudo-Smites!). I'm thinking something along the lines of an Adventurer feat that grants you a second Fighter Maneuver, and a Champion feat that provides a third and opens up the Champion tier options (5th and 7th level Maneuvers). The Epic feat would follow suit, granting another Maneuver and opening up the 9th level pool.
This obviously has the additional effect of increasing the Paladin's complexity a little bit, which is attractive for those players who find the basic Paladin too simple.
This time the base benefit works fine, but the Invocation could use some tweaking! In place of "daily spell," I'l allow a roll to recover any other daily ability the Paladin has access to. This could include a Cleric spell with Cleric Training, but Lay On Hands is also fair game. Any use of Smite Evil beyond the one you get per battle for "free" would also qualify. Ultimately it's a pretty straightforward conversion (and at minimum all Paladins will have Smite Evil, so it's a good general-use domain, especially for Paladins who can't get past the fluff of Way of Evil Bastards but still want to Smite a lot).
While this domain might not fit the fluff of your archetypal Lawful-Good, Knight in Shining Armor, there's no denying that it's a powerful option for any Paladin. It's a good thing 13th Age doesn't shoehorn you into the goody-goody role ;)
The Trick Die is great as a party buffer (if you roll high) or enemy debuffer (if you roll low), both of which fit the Paladin's expected secondary role just fine. The Invocation will only serve to make you even harder to kill than you already are. Your GM won't be happy, but if you like being an impenetrable fortress with legs this'll help.
This is another great domain that requires no modification and can easily fit the flavor of almost any Paladin. You won't get a much more reliable party buff (every time you attack), and the Invocation is probably the strongest of all the Cleric Domains. Just make sure you time it right; certain classes don't like when you increase the Escalation Die before they get a chance to use an ability that keys off of its value (the Fighter's Counter-Attack when it's even, or the Wizard's Cyclic Spells).
Bonus: Arcana/Mysteries Domain
This domain (and the next one) are from my "13th Age Options: The Cleric" article. It seems a little harsh to make a Paladin first pick up the Cleric Training talent to get a Cleric spell, and then pick up Divine Domain to swap it for something else. That's effectively one talent for the price of two, and it's nowhere near as good as the Ranger's animal companion (the only talent so far that costs 2 talent slots).
It's an easy fix, though; just let the Paladin swap out one of its limited-use abilities. One use of Lay On Hands, or one of your daily uses of Smite Evil seems like a fair trade for most spells. Obviously there's potential to pick up an option that's much more powerful than what you gave up. If it seems like it'll be too game-breaking, forfeit two daily uses of Smite Evil for a single spell, or limit the spell to one that's 2 levels lower than you (like the Sorcerer's "Access to Wizardry"). Remember, this game isn't about power-gaming, and while it's pretty resistant to min-maxing that can go out the window when you start swapping options between classes. You don't want this to be a go-to option for any Paladin in your campaigns because it just happens to be that good. It should be a roughly-balanced tradeoff for a Paladin that legitimately has a connection to arcane magic as part of the character concept. Maybe they have a background "Former Bodyguard of the Archmage," or their OUT is "I'm the botched attempt at creating a super-soldier through powerful arcane magics." Let 'em take this domain to back that up!
Bonus: Focus/Fortitude Domain
Paladins don't have much in the way of spells that they can prepare multiple times. This domain is going to be a lot more niche than most even with tweaks, but for the Paladin who picks up Cleric Training, the Arcana/Mysteries domain, or Lay on Hands this can let them tweak which options they have access to each full heal up. For example, they can prepare an extra use of Lay On Hands by sacrificing a daily Cleric spell, or a spell gained from the Arcana/Mysteries domain. For Paladins that only have one such option (we'll use Lay On Hands for our example again, but this time the Paladin has no spells), swapping for those daily uses of Smite Evil is a good idea, just like in the above Arcana/Mysteries domain.