Level 12 Analysis
Your AC is very low. At level 12, AC 18 is essentially a death sentence. I'm going to assume you have a source of Mage Armour from a party spellcaster, giving you an AC of 22, and a further Ring of Protection or Amulet of Natural Armour or Barkskin or something to up that by +2 to 24. 24 AC is still incredibly low.
The lowest attack bonus I found with a quick peruse of CR 12 monsters is +18, the secondary Bite of an Athach. That hits you on a roll of 6. The most common number I found was +23, which would hit you on a 2. I saw lots of +26, +28 and even a +33. Those all hit you on everything but a natural 1.
In other words, your AC is too low if anything targets you for you to survive. The DM will have to pull punches not to kill you.
Valiant Stand improves this. By not by enough. Enemies are still going to autohit you. Best case is +4 stat boosters on dex and wis, mage armour, nat armour/deflection bonuses, and valiant stand - 18 base, +4 from enhancement to stats, +4 armour, +2-+3 nat armour/def, +3 valiant stand = 32. That's a hit on a 9 from the lowest common attack bonus I found on CR 12 monsters.
Your Attack Bonus Is Pretty Decent, For a Monk. You have +16 to hit without Smite. With Amulet of Mighty Fists +2, that's +18ish to hit. With Belt of giant Strength +4 or Bull's Strength, that's +20 to hit. Everything that has AC that is supposed to be a defense has 26+, which is good - you hit most of the time. Power Attack and Flurry are counterbalanced by Valiant Stand, which you should be endeavouring to have always active by use of Stealth, which you don't have maxed out, uh, why? Popping up out of nowhere for a flatfooted smiting power attacking flurry should be your opening round action in every combat. Even your iteratives have a decent chance to hit, with this hit bonus. Only decent, though.
Your Damage Isn't Great. 1d10+1d4+5 (where is that errant +1 damage coming from?) averages out to 13 points of damage per strike. With Power Attack, that's 19 damage. With Smite, against evil or chaotic outsiders/dragons, you get /+18/, so 34 damage per strike, which is actually level 12-worthy. Too bad you get 3 total attacks per day with that damage. Sweeping Smite carries the Cha-to-hit bonus, but not the damage from the 'first hit'. It's kind of like a really terrible whirlwind attack that way.
Most of the time you'll be attacking for 19, on average. Some stuff is immune to bleed, or has DR/cold iron and good, etc, so it might be less. If you move, you only have one attack, so your first round barring stealth will nearly always be one attack at best. Rounds after that, you can flurry for four attacks, each which might hit for 19 damage.
So a max damage on an ideal round of around 34+19+19+19 damage, or 91 damage in 4 hits. That's not terrible. It relies on getting a full round action, though. It also relies on hitting with iteratives, DR of the kind you can get past, no miss chances etc. Most monsters at this level have at least 150hp, so you won't be winning in hp races. But you will be able to contribute a bit at least to the usual team of four on one beatdowns.
Your HP gets eaten in a round. With your AC, most CR9+ melee monsters are going to kill you to dead in a round. 11 Constitution on a melee combatant isn't a great idea, but then, you're a monk and need wis and and dex and str and also cha for being a paladin, so eh.
Your Saves are decent. They could be better, but they could also be worse. Most DCs seem to hover around DC 23 at this level, going up as high as 28 but also as low as 21. With your +11/+11/+13, you should have a 50% shot at most saving throws, and although fear and poison aren't exactly the most common life-threatening things to save against, it's still nice.
Power Level: Fighter.
This character can be relied upon to be roughly as good as an unoptimized fighter. The DM will have to pull some punches, and tough encounters (CR +2 or greater) will have a good chance of one-shotting this character by accident. In a party with Rogue or better power levels, this character will feel notably weaker than the rest of the group.
Note
Evaluating something without gear is hard, because at the lower end of the scale, gear can have more effect on your ultimate spread of numbers than the classes chosen. If your gear is random stuff, you will be weaker. If you plug it all into boosters for your FOUR necessary stats (dex, wis, str, cha), rings of deflection and other stuff that helps boost your melee stats to make you 'great' at that rather than 'mediocre to good', which includes buffs from friendly spellcasters, you will be stronger.
Note
This build is stronger at lower levels, where a handy Mage Armour plus your defensive stats can put you out of reach of opponents attack bonuses, and things are easier to hit and easier to kill. Level 12 is definitely where things are starting to go 'downhill', and they will likely get worse as enemy AC and AB increase and every enemy has flying or spells and abilities.
Note
The build has no movement capability other than skills-based climbing, swimming, jumping. I'm assuming again allied spellcasters will be patching that hole with buffs, especially since with the other gear i've assumed in your build you don't have the money to buy gear to get flight or teleport or whatnot.
Suggestions
Your main problem is that you're playing a monk. Without serious optimization, monks are very weak. You've done a bit of optimization here, and pushed it up to unoptimized fighter level, but fighter is still not great if you're planning to be in a party with casters. Or if you're fighting caster-style enemies like many demons are.
Most of the tricks I know to make melee characters more competitive are in 3.5e. I'm assuming there's no backward compatibility in your group. So that's all out the window.
Paladin isn't giving you much other than flavour, either. You've got a decent Flurry and Attack Bonus, but you're way too fragile to make good use of it, unless your enemies come in the 'always attack the guy using the full defense action with the tower shield' variety.
In this case, i'd recommend Summoner. Synthesist Summoner. It slices, it dices, it buffs, it has level appropriate abilities, natural attacks, the works. It is, in fact, so good that you could mix it with a Paladin dip and still be relatively awesome.
Evangelist lets you keep advancing as a Summoner while also adding a divine feel to the class. It's also the only prestige I can find that advances your eidolon aka living armour, so.
Other. than. that... there's a good rogue-based fear build, but I don't know how relevant that is to your concept.
I feel like there's some way, between Fighter archetypes and the Hungry Ghost Monk monk archetype, to create kama-wielder who reaps ki from his opponents and uses it to chain-stun them with a huge Wisdom and Dex, just whittles them away with flurries of weak, ki-reaping attacks and then spends the ki on stuns. There's too many damned archetypes though.
Even if you're taking summoner, it's kind of worth dipping monk as well. You have to be unarmoured to use your synthesism, so you could benefit from a high wisdom score to your AC. Not worth going Hungry Ghost, because the ki-drain only comes at level 5. Just a one, or at max 2-level dip. Probably after you have 1 or 3 levels of synth summoner.
Yeah I cannot find anything that is about punching people that isn't just a Fighter or Barbarian with a 2-hander sword that is any good. There's some rogue stuff that is nice, there's an alchemist archetype that gets sneak attack and would make a murderously effective hand to hand combatant with the mutagen and the buffs. But nothing based around jumping on things and punching people except synth summoner. Yeah. That's my advice.
Synthesist Summoner 20.
Optional; Monk 1.
Optional; Evangelist.
Best Answer
On the feats you suggest:
Fey Foundling—not really worth a feat for you. It would boost your lay on hands self-heal a fair amount (averaging 2¾ HP/level instead of 1¾ HP/level), which could be worth it for a character hyper-focused on self-sufficiency. But it does nothing for your damage, your protection from non-HP threats, your protection from one-shot kills, or your ability to heal allies, and it comes with a drawback (albeit a minor one). You can do a lot better than this in a feat, and you need feats way too badly.
Greater Mercy—terrible feat, at least in the long term. An extra 1d6 HP healed is nothing past the earliest levels. At best you can take it at 7th, when it represents a 25% improvement in your lay on hands healing, which sounds good until you remember that your healing is already rather low. 25% of a little still isn’t a lot. And the proportional benefit drops fast.
Power Attack—not amazing, but it may still be the best you’ve got. Only use this when you have both hands on your weapon; the accuracy penalty isn’t worth the damage unless you’re getting the two-handed bonus.
Extra Channel—you should not need this, you should have high Charisma. I would only get this if, after several levels, you determined you really really needed it on a daily basis. Remember, you still want a wand of cure light wounds, so you should not be burning through your channeling that fast.
Much more valid option if your GM allows you to retrain. Getting it early (when you are getting little from the half-level component and you cannot afford to boost Charisma yet) could be worthwhile, and then you retrain it once you are better-situated.
Antagonize—if you say this will work reliably with your GM, I cannot gainsay that. But if you aren’t looking to be the party face, that’s a lot of skill points devoted to making this work, and it will fail against a lot of targets, and it’s costly to use in combat. It’s the right idea for you, but I worry about it being effective enough to serve its purpose.
Weapon Focus—the only reason to ever take this feat is as a prerequisite to something else. Even then, you can just buy it for 2,000 gp, with a cracked opalescent white pyramid ioun stone and a wayfinder. Note that the cracked opalescent white pyramid ioun stone also gives you the ability to use some weapon as if it were martial, so feel free to grab a decent exotic if you can actually find one (you probably can’t, exotic weapons in Pathfinder are universally awful).
Selective Channeling—you should not be channeling energy in combat. It just doesn’t do enough. Kill the things you don’t want to heal first, then start healing. If channeling energy was an effective choice in combat, this would be a good feat, but it’s not so this isn’t.
Step Up—finally, a truly good feat. Yes, get this. Get this as soon as possible, do not wait until 15th level to get it.
Cleave—this feat is absolutely awful. You need to be full-attacking, not wasting a standard action to attack once. If you find yourself forced to move and thus left with only a standard action, cast a spell.
Great Cleave—see Cleave.
Improved Critical—happen too rarely to invest in, you have no special bonuses triggering off of criticals, and you probably are not going to be using a high-threat-range weapon. Why would you take this?
Angelic Blood—useless, but...
Angel Wings—this is fantastic. Angelic Blood is not worthwhile on its own but Angel Wings may very well be worth two feats. You need to get into the air somehow.
My suggestions:
Power Attack—it’s the basic damage boost. Not great but we’re only just getting started. Note this basically requires you to use a two-handed weapon, and is thus not necessarily compatible with every other option here.
Antagonize—if you say you can expect it to work reliably, the effect is good.
Step Up—this feat remains amazing.
Following Step—ok, not amazing. The Dex requirement is really sad for you, but can be worth it because...
Improved Bull Rush—not bad, as moving your foes away from your allies and putting yourself between them should go a long way towards protecting them. Usual problems with the combat maneuver math hurt here: at higher levels, CMB just doesn’t keep up with CMD and it becomes very difficult to succeed. Smite’s bonus to attack also applies to CMB, though, which does help.
Focused Discipline—this feat is mediocre without the stamina rules, since fear effects aren’t used that constantly, but you’ll always pass and if you have the stamina rules, you can use it without anyone fearing you. The bonuses are only decent, but there are slim pickings at this point. Still better than, say, Weapon Focus.
Angelic Blood—as noted, awful on its own, necessary prerequisite.
Divine Fighting Technique—without knowing what gods you have available, it’s impossible to say which of these you can take. The big ones to look for are Desna’s (which the SRD calls Way of the Shooting Star), which allows you to use Charisma for attack and damage with starknives, and Gorum’s (which the SRD calls Greatsword Battler), which allows you to use Vital Strike at the end of a charge. Note that neither of these would be allowed to a paladin in Golarion, as these gods are not LG and the feat requires that you match the deity’s alignment.
If you take Desna’s starknife ability, the Charisma to your attack stat does not stack with smite. This is antisynergistic, because instead of getting Str+Cha to attack against a smitten target, you get only Cha. However, that makes for a great reason to use the sacred shield archetype: your smite isn’t as good for you anyway, so bastion of good becomes a much better deal. Note that this also affects combat maneuvers, as combat maneuvers are attack rolls, which is nice. Starknives can also be thrown, which is well worth considering.
If you take Gorum’s greatsword charging ability, you will want charge feats (most importantly, Spirited Charge) as well as the Vital Strike line. These feats are ordinarily rather poor on their own, but by being able to use both at once, they become much, much better.
Dirty Fighting—I save this for last because some GMs may decide to houserule this away from paladins. That’s awful, though, because despite the name, there is nothing particularly dirty about this feat. Instead, what it is is a lot of versatility in one feat. It means that no combat maneuver provokes for you if you’re flanking, and it counts as having Combat Expertise, Improved Unarmed Strike, Dex 13, and Int 13 for prerequisites, helping you improve them. It gives you a lot of flexibility, and smite gives you bonuses to CMB for any maneuver. Unfortunately, this feat is not yet on the SRD, but only found in Dirty Tactics Toolbox.
Barroom Brawler—again, names that don’t sound paladin-y, but an effect that’s perfectly suitable. This allows you to get a combat feat temporarily, allowing you to meet a lot of situations you wouldn’t otherwise be prepared for. This is a very good feat.
Improved Trip—tripping is fairly effective, particularly at low levels. Definitely not worth getting Int and Dex in order to take this with Combat Expertise. Really, really wants a reach weapon.
Combat Reflexes—if you really want to trip, this is how you trip well. Requires a fair amount of Dexterity, though, even more than Following Step and Step Up and Strike.
Improved Dirty Trick—Dirty trick is slightly “dirtier” than Dirty Fighting itself, but it’s also the best combat maneuver (just because of its versatility) and ultimately, nothing about it is any more underhanded that flanking, surprise rounds, and any number of other combat advantages that paladins are allowed and expected to enjoy. Definitely the best choice of combat maneuver if you go with starknives.
And something somewhat different:
Ultimately, the paladin has some fairly-solid defensive abilities in the form of divine grace and the auras; you do not need to spend feats on defense. Your out of combat healing is, similarly, quite adequate out of the box, and you do not need to spend feats on it. In-combat healing just isn’t effective enough, only useful in niche emergency situations. In those situations, just do what you have to do, but your feats need to be devoted to things you do all day, every day. Instead, my recommendations are devoted to eliminating threats as quickly as possible, and sticking to them in the interim to limit their ability to target your allies as much as you can. This matches your stated priorities, and is I think the most effective options you can take.
Unfortunately, as for order, that depends a lot on whether or not you can and want to use any of the Divine Fighting Techniques, and/or whether or not you can and want to leverage Dirty Fighting, and/or whether or not you are using the optional stamina point rules. Step Up is definitely something to take ASAP, and Power Attack and Furious Focus are similarly always-solid options. You say Antagonize will work for you, which helps a great deal. So those feats make the most sense as your top priorities no matter what.
But if you’re going with starknives, you want that ASAP because you want to dump Strength—which also means you’re probably not doing Power Attack. With Dirty Fighting and Barroom Brawler, you could do decently with combat maneuvers (aside from trip, which suffers so much without reach), particularly dirty tricks. Without, the archery line is almost-certainly your best bet there. Note that throwing allows you to combine both archery and TWF feats, but you probably won’t/shouldn’t have either the Dexterity or the feats for that.
Alternatively, if you can use the greatsword charging option, suddenly mounted feats and Vital Strike become high priorities, when they wouldn’t be taken at all otherwise. Most likely in that case you would want Power Attack, Furious Focus, Divine Fighting Technique, Vital Strike et al., Mounted Combat, Ride-by Attack, Spirited Charge, which will use up pretty much all your feats.
If doing neither, but allowed Dirty Fighting, getting a bit of Dexterity so you can trip as well as use the Step Up line seems in order. That will allow you to harass the opposition well and keep them off your allies. Remember that reach weapons are also two-handed, so you can and should still take Power Attack and Furious Focus. And Barroom Brawler is fantastic flexibility.
If stamina is in play, Focused Discipline is a quite-good feat for you no matter what you do. Without stamina, it’s lack-luster but still OK-ish. Fear happens enough.
And without any of those things, Power Attack, Furious Focus, Step Up, and Improved Bull Rush look best. Improvements to bull rush and Step Up follow those. Well, actually, at that point, archery is best, but besides that.