The biggest issue with paladins is when their partners' behavior is judged as if the paladin himself had done the deed. If your DM is willing to avoid that pitfall, may I suggest...
A paladin who does not expect non-believers to obey the laws of his faith. He hopes that through his shining example his teammates will come to see the value of his code, but believes that doing Good under threat of punishment doesn't count. He guides the party to consider mercy, but does not expect them to follow oaths they did not swear. Perhaps his own past is not lily-white and he recognizes that true Faith takes time; he is patient with the party.
Underen commented: When the PCs ignores the paladins advice, simply tell them in character: "Remember, the gods will be the judges of your actions. I wash my hands of this.
It's important to recognize that the values of D&D are not our modern values. Justice is often swift and brutal when you don't have the luxury of modern civilization. Think wild west justice or battlefield trials. As a paladin, you might have the authority to conduct hasty trials; ask your DM to consider this1. Remember there are methods of punishment that fall between letting criminals go unpunished and killing them: from taking their stuff, to branding or even cutting off a finger or a hand2, there are a spectrum of options.
Just as you are considering the enjoyment of your friends at the table, the DM and other players should be willing to meet you half-way. The player characters should do the same for their friend the paladin. This is a mutual storytelling challenge: a group of friends (or at least comrades-in-arms) with different moral attitudes is pretty common in real life and in storytelling. How do they function without coming to blows? That's a cool story for your group to tell.
Making the Tough Decisions is an essay by Rich Burlew which addresses (in more general terms) the exact problem you're facing.
1 There can be some confusion about the paladin's requirement to "respect legitimate authority," and whether one's class dictates in-game social duty or privilege. As I understand it, 'Paladin,' 'Cleric,' and all other class titles are meta-mechanical terms rather than in-game titles/distinctions unless you're in a setting that makes it explicit. Thus no character (player or non-player) has legitimate authority by virtue of their class alone (there
are some rare PrC exceptions to this, whose explicit nature supports my general claim). Authority is conferred based on merit, heritage, experience (and possibly bribery). My suggestion that your paladin might have some legitimate authority is explicitly at the whim of the DM. It could just as easily be bestowed on a bard or a fighter, should social circumstances warrant it, and serve the same purpose --perhaps even better.
2Perhaps I should clarify that branding and mutilation in these contexts are not about sadism: they are about preventing future crime without killing the criminal, in a land without good jails. Brands alert future targets that they are dealing with a particular kind of criminal, and cutting off a gun-happy outlaw's trigger finger makes it harder for him to kill.
A Radically Different Idea
Your player had fun playing a greedy awesomedwarf? And now isn't having fun playing a Stop Right There! Paladin? Easy.
Have him take that in-character.
Whoa, whoa, what are you talking about?
Simple. Have the paladin start to be dissatisfied with the course he's taking. Have him start bucking authority, becoming a dangerous loose cannon. Going a bit far. Being reckless. I'm directly quoting Lethal Weapon here, because that's what you want to be. Martin Riggs is the ideal Paladin-walking-a-darker-path. He wants to be Good, and Lawful, but there's just so much darn Evil out there, and it's hurting the innocent. So many good reasons to just cut that moustache-twirling evil guy's head right off, and not give a damn.
Maybe the Captain of the Town Guard calls him in and lectures him and threatens to just stuff him in prison - maybe it's his direct superior in the paladin order. Either way, you do your part by having authority figures drive him further towards vigilantism, violence, and using evil means to defeat evil, and he can do his part by playing a conflicted, confused young man treading a path that leads to darker acts than his foes can even dream of - all in the name of Good.
And then you end up with something a bit deeper than a black suit of armour with a different flavour of boring character inside.
Best Answer
There is a feat that grants lay on hands 1/day it is called Believer's hands. It's prerequisite, believer's boon (directly above believer's hands) grants one use of a 1st level domain ability granted by your god.
For making the magus more paladin like I'd suggest taking the eldritch scion archetype with the celestial bloodline. Even if its Angelic Attacks is by far weaker than smite evil it at least lets you ignore some DR and deals more damage to evil outsiders.
An option to become more paladin-like would be the chevalier prestige class. But as it doesn't increase spellcasting that would, most likely, not be the best choice optimization wise.