All the "orientalism" arguments that have been said regarding the Monk could be used, slightly modified, with the Paladin.
Well, it's worth noting that I removed the Barbarian, Paladin, Ranger and Druid from my game because I also felt that they carried to much cultural baggage to be a true base class. The concepts of those classes remain in the game, but as the more generic and versatile Fanatic, Champion, Hunter, and Shaman which are not specific to any single culture. You can still make a berserker northern barbarian by playing a Fanatic, but you could also play a knight Templar, a member of the King's elite bodyguard, a whirling dervish, or an insane cultist. You could make a Paladin character by playing a Champion, but also a batman style vigilante or a paragon of evil. And so forth.
So, I'm not being hypocritical here. You may be right about the Paladin being too specific to a setting, but that doesn't make the monk less problematic. If you really wanted to play a monk in my game I'd say, "Alright. Play a human or hobgoblin fighter. Spend your starting trait on Unusual Background (Martial Artist) to add Balance, Tumble, and Concentration to your class skill list, and start play with Superior Unarmed Strike and either Skill Focus (Unarmed Strike), Toughness, or Brawler. Focus on going up the unarmed combat tree - One Two Punch, Roundabout Kick, Deflect Arrows, etc. - with a particular eye on Lethal Weapon at 6th level and eventually getting Hard as Nails going up the toughness tree. The Riddle of Steel might also be an early option for you, as might Acrobatic Attack particularly once you get One Two Punch. Powerful Charge and Jump Kick also make a good combo. You might want to consider dipping for a level of Explorer to maximize your number of attacks, or you could go crazy and multiclass into Sorcerer for Arcane Strike, Enlarge Self, True Strike, and Body Weaponry. Alternately, dip cleric, abuse Interdisciplinary Student, and head for Persistent Spell."
I've actually had a player consider a build like that for a while before going with a more traditional. It's not something I fully encourage with the rules because honestly in the real world swords are better than fists and frankly I find the Kung Fu thing a bit hokey in a way I wouldn't find playing a sword or staff based martial artist. On the other hand, I have also had an NPC built along the Sorcerer/Martial Artist lines that was one of the campaigns mini-bosses, so it's not like I'm not cognizant of the style points. And heck, if I was a PC in my own game, I'd be strongly considering a Idreth staff based martial artist as my character, and the Idreth really are culturally prone to what humans would call monasticism.