The Blood of Fiends companion book states (page 10):
Most tieflings born into the Worldwound proper are enslaved or consumed, and those in surrounding lands are harried from hamlets and towns where they might otherwise live quietly, and generally head a little farther south or west each time to seek a place where they can hide themselves anew.
You can also read on paizo forums James Jacobs's opinion on how NPC paladins would treat a tiefling paladin, particularly around the city of Kenabres:
The way the other paladins are supposed to act toward him depends on the other paladins. Not all paladins are the same. The generalized feel toward tieflings in the Worldwound IS to not trust them, though, so a tiefling paladin will want to be VERY obvious about it and should expect to get the detect evil eye all the time and should work hard at building his reputation.
... Kenabres's attitude toward tieflings is a city trait, as detailed in GameMastery Guide. ... Basically, in Kenabris, Tieflings pay 150% for anything they buy and face mockery, insult, and perhaps violence.