There are several different themes you could work with.
1) The typical, pick a hero (pokemon), fight it out on lanes, etc.
2) Pick a trainer/hero, who then can choose to learn a variety of moves, based on the pokemon he gets.
3) You could also do a thing where the pokemon trainer is in the background, and you send out different pokemon, all of which share Exp, HP, items, etc, a la SSBB.
Any of those would make players open to trying your map, if only for its originality. Cause honestly, if there's one thing the wc3 mapping community doesn't need, it's another DotA, imo.
Yu Gi OH:
could be awesome, models are good here, find a modeler to help you on this or you could just take dragon from the Warcraft and name it, Blue Eyes Blue Dragon whatever his name is lol
can be used as trainer, catch your pokemon, and then it can be your main pokemon and you could get more something like that, OR you could catch pokemons, then they turn into an ability on the trainer (hero) then you summon the pokemon to fight with his own abilities, or it could just be a Pokemon that farms and you control it as a hero
OR, because you brought up the ninga one, no one did a Ninja AoS ^.^ choose man its ok if it turned out crappy, you could just change the units