Interesting ideas! I like the concept. And the mental image of a bunch of legendaries standing around you with gifts, cards, flowers etc. is hilarious. Between the legendaries and the father with two lovers and his kid's mom off somewhere else, sounds like this will be quite humorous along with being an intriguing plot. There's only one detail that you should probably think about:
Even if we take "teenage" to mean the youngest teen possible, a 13-year-old, Paul would have to have been 12 when the player was born, and possibly even 11 when he impregnated the player's mother. Teen parents aren't exactly uncommon--and considering that Paul has two not so secret lovers separate from the player's mother, I'm guessing a teen parent wouldn't be taboo in your game. But, a preteen parent is very unusual. Unless you really want Paul to have been a 12-year-old or younger dad (which would be something you'd want to reflect somehow in his characterization), you might want to change an age. You could either make the player the "normal" age for a Pokémon player, 10-ish, so that Paul could be 15 when the player was born; or, you could make Paul a few years older, 29 or 30, so that he could be 16 or 17 when the player was born.
I'm also wondering about why you'd need to make two different gym leaders based off of the player's gender. Is it something like R/S/E, where if you play as male, then May is a rival, and if you play as female, then Brendan is a rival? Because if Nina/Nikko served as an ongoing rival, acting as the character that you didn't choose, her/his alternate genders would make more sense. But if she/he is a character that you only run into once, just to get a badge, then giving her/him a variable gender and Pokémon type wouldn't make as much sense, since it wouldn't really have any long-term effect on the game.