Probably the general lore reason that orcs don't have a paladin class available is that the standard in-game, playable green-skinned orc is supposedly a mag'har, brown-skinned orc that was corrupted in the past by demonic fel magic. Since the source of a paladin's power is supposedly from the Holy light, it would seem an orc with the remnants of fel energies would make them incompatible.
The green skin is more a sign of having been exposed to fel magic, but not completely corrupted. Eventually, long exposure to fel magic will turn an orc into a fel orc.
Since the blood elves managed to use a captured naaru as a source of Holy light to maintain the powers of their blood knights, it may be possible at some future date for the orcs to do the same, but they have expressed no interest so far and have shown little interest in the Church of the Holy Light from which most paladins arise.