If you're willing to borrow a fairly reasonable half-breed from Pathfinder you can get 6/10 for sure, probably 7/10, and maybe all of them without any magic or unpleasantness at all (for you).
##Step 1: Get in good with the Green Hags. ##
Yah, this doesn't sound like a very good idea. Hags in general "are horrible creatures whose love of evil is equalled only by their ugliness" (Monster Manual, 2003). They also "may turn on their master if they see a chance to seize power for themselves" and "do evil for its own sake". So basically, by just considering this you've already lost your Paladin levels.
Fortunately for Our Hero, Green Hags are *definitely* the most attractive of the bunch (of the hags, that is), lacking both the Horrific Appearance (Ex) of the Sea Hag and the Rend (Ex) and Rake (Ex) abilities of the Annis (not to mention her 325 pound weight). Given the description, this means they must also be the least evil, not that that means you get your Paladin levels back.
The main issue at this step is that the hag or hags might just decide to kill and eat you or otherwise not cooperate in this whole procreating business. Assuming you (you *are* the prince) figure out some way either to woo yourself into a hag's actual good graces or temporarily defuse the various attempts she makes on your life, mind, soul and kingdom long enough to produce a child, we can continue. Like all hags, Green Hags can cast *disguise self* at will. They also have a 14 base Cha and a 12 base Dex.
##Step 2: Raising Your Daughter##
The child is a [changeling][1]. Changelings are clever and comely, good traits in future Princesses. They also aren't inherently evil, which is good if you still care about that. Changelings grow up fast, and hit adulthood at age 15, just like humans.
##Step 3: Profit##
If you talked your GM into letting you keep your paladin levels from before (or got an atonement), you're losing them now. Your daughter can definitely reproduce with the Bugbears, Halflings, Dwarves, Centaurs, and Locathah. ("Depending on the race of her father, a changeling can resemble any type of humanoid, including dwarves, gnomes, and even orcs and goblins.") She can probably reproduce with the Aranea (From Change Shape: "The first is a unique Small or Medium humanoid"). She might be able to reproduce with the Pixie, Cloaker, and Beholder, depending on your definition of 'man' ("When a hag of any sort conceives a child with a man, the result is a changeling").
Because her mother was a Green Hag, she even "gains a +2 racial bonus on Bluff checks against creatures that are sexually attracted to her".
## Step 4: Plan B ##
If, for some reason, your GM rules that beholders and such are a bit much, it's time to step up the game. You *do* have a Cleric, so have him call up a succubus with Lesser Planar Ally (you'll have to get one's true name, but that shouldn't be *too* hard. You could settle for whatever demon/devil his deity feels like at the time, but you really want your side to be the female, so you have custody of the offspring until it's born and nothing fishy happens. This is in fact the entire point of using Planar Ally, if you're ok with the other race having initial custody, you could do it with Summon Monster II for a Lemure, combined with some caster level boosts for duration and something to make the other party agree to this). Fiends can breed with any non-good creature (MM p. 147), so this nets you the beholders (at the cost of there now being half-fiend beholders in the world) and the cloakers.
## Step 5: Plan B, Part 2##
This leaves only the pixies, who are neutral good, beyond the reach of your unholy alliance. Have your wizard craft a Helm of Opposite Alignment, kidnap the Queen of the Pixies, stick it on her, and proceed as above. Or summon demons to tempt the pixies into evil. Or whatever.
## Step 6: Receive Obeisance##
You are by now King of a nation (you did off your older brother during this, right?) whose grandchildren rule each of the surrounding nations. If you can somehow keep your children loyal to your lineage and otherwise under your heel, you have consolidated control of the entire region once your grandchildren take over the leadership roles of their respective societies. At this point you can turn your attention outward, sending your daughter and other emissaries to nearby humanoid lands, while you continue to enjoy the spoils and dowries of 10 tiny nations. Make sure you keep that rogue around, though: those hags are gonna backstab you sooner or later.
------
All of the above is doable without access to changelings or, technically, evil summoning spells. You could instead mass produce helms of opposite alignment and convert the princesses of the neighboring nations to the side of good as needed, summoning a Lantern Archon (4th level spell) instead of a Lemure, or calling a Bralani instead of a succubus. Even if you do this, however, if I was your GM I'd seriously investigate your justifications/reasoning because you are basically raping the leaders of every surrounding country in order to use your shared offspring for your own political gain. If you can somehow diplomatically generate consent from the ruling parties of all 10 of your neighbors, then that's a different story, but several of them (hags, beholders) seem to have evil as a part of their essence. I doubt your ability to accomplish this and remain LG Pal 4, Crusader X, but I suppose it is possible.
[1]: http://www.d20pfsrd.com/bestiary/monster-listings/humanoids/changeling