I'm trying to create a Half-elf Paladin born and raised in Ustalav. I know that such combination in that region is very unusual, but I seek a logical explanation to account for such a PC. Any suggestion?
Well, both Ustalav and Kyonin have shores along Lake Encarthan, which is a body of water with a whole lot of trade going on. So getting someone from Ustalav together with an elf doesn't seem that difficult. Particularly since Desna has quite the following in Ustalov (which could encourage a young man to take up sailing at least once in his life..and maybe fine a nice long haired lady friend along the way....).
The Knights of Ozem in the nation of Lastwall are also a good excuse for being a paladin. You know, the group whose main thing was defeating the evil lich that ruled over Ustalav with an iron fist (as well as orc-y grunts). The fact that there are a lot of undead boogaboos running around ustalav seem like it leaves a lot of opportunities for a kid to want to be a paldin (burning with a heart filled with either vengeance or admiration, depending on the direction you want to take the character).
So it shouldn't be too hard to get all these elements together.
I'm not sure why you'd think it's so unusual. Many of the Core races seem to be pretty common in Ustalav, Human and Dwarf especially but Half-Elves and Halflings too I'm certain.
And lots and lots of half orcs.....again, orc-y grunts.