Greece, obviously. The greek mythical potential for pokemon is astounding.
>twelve legendaries based off of the Olympians
>assorted regular pokemon based off of nymphs, sprites, spirits, greek heroes/poets/philosophers (four elements and humors)
>psuedo based off of Hercules or any of the other many Demigods (Aeneas, son of Aphrodite as a fairy/fighting, Theseus, son of Poseidon as a water/fighting, or even Helen of Troy, daughter of zeus as an Electric/Psychic or Electric/Fairy)
For fuck's sake the evil team could even be centered around utilizing titan legendaries, like based on Kronos and Hyperion and Ouranos.