A prophet is an excellent duo with pretty much every melee class, so yes.
As far as a buffer/paladin duo goes, I might be more tempted to run with a Warcryer. The buffs aren't as extensive as the prophet's but a Warcryer brings a fair amount of offense to the table as well, as opposed to the sub-40 heals a prophet has, which COULD be seen as redundant as the paladin can heal himself. Couple the paladins heals with the extensive regeneration buffs of the Warcryer as well as the Warcyer's life-drains and DOTs and I think you increase kill speed a substantial amount while still having a minimum of downtime.
This, of course, is just my opinion; which is to say that, although I'll never admit it, I might be wrong.