You could only have an Illithid paladin under very select circumstances.
"Don't... No, please, no! Heironeius have mercy on me!"
First off, he would have to have been born in to the body of a paladin through ceremorphosis.
<Earcanal sweet brainmeats eat yes>
The tadpole kills the paladin by devouring his brain.
"AAAIAIGHGHHALALALALLALlglglgllll.... lll... ll...."
From there it replaces the paladins brain and matures in to a healthy young illithid - Their equivalent of an adolecent, having only just gone through their equivalent of 'puberty.'
<Feed warm stay grow skull consume yes>
And the soul of the paladin clings. Desperate. Refusing to leave, haunting the only thing left to him: His corpse.
And the taste of brains grows foul. The screams of agony start to set up empathic vibrations in the mind of the hero-spawned illithid. He cannot pierce the skull of a slave without feeling the overwhelming terror and despair and FEAR of it, sending him in to dry heaves and spasms.
He must flee. He MUST escape. He must... Must atone. For years, decades maybe, of unspeakable evil, of creating pain and agony almost indescribable on creatures helpless to resist.
An illithid paladin, almost by definition, must be completely and irrevocably insane. His wisdom score must be reduced too low for spellcasting, but his overwhelming charisma mods will make up for that weakness... Deluded as to his own nature, only saved from starvation by the blessings of Heironeius, sometimes thinking himself the spirit of his corpus and other times recalling his true nature and the self-disgust that comes with it, an illithid paladin would die unloved and uncelebrated by all except his patron deity, who would grant him a final and lasting forgiveness, allowing him to rest forever in the peaceful afterlife, the hunger to feed at last removed.
You'll definately want to get him a ring of sustenance. But to him, this ring is the Ring. Without this ring, he becomes a monster. Anyone threatening to take it is killed, instantly. And he will be hunted for sport by his kin, who are amused at his madness, until he grows strong enough to slay all who stalk him.