I'd rule that he uses spell-like abilities at his character level, so a 10th level paladin/2nd level cleric can detect evil as a twelth-level caster. This fits the "equal to the HD" requirement in the MM. I could see (and would even likely use) a house-rule only counting actual paladin levels, but strictly speaking that one does not have support in the rules.
Spells are different from spell-like abilities as far as caster-level determination are concerned, so a definition of the paladin's spell-caster level in the "Spells" section of the paladin character description does not, for me, determine his spell-like ability "caster level". So detect evil, remove disease, summon mount, etc. are not 1/2'd in my campaign (in fact, Summon mount specifically mentions the "paladin level" as relevant -- which might lend support to the "paladin level" house rule as outlined above for detect evil and remove disease). Ymmv. But I think the rules don't contradict my position.