I would love a Kangaroo based Fire starter but it would have to be Fire/Fighting
Also one of three posibilities for water starter
A Frog, Water Poison
An Elephant (with tentacles!!!) Water Rock
OR A Crab, with a triple branched evolution to a Water Type lobster thingy, a Rock type Crustle-esque Pokemon or a Water/Steel ultimate Crab.
Also a Grass type that evolves to a bipedal tree, MARCH OF THE ENTS!
I would have two possibilities for the regions bird, a slow, high defense Pokemon or a Really fast Falcon Pokemon with really low defense.
finally legendaries based on King Arthur and the round table, with a Dragon/Steel for Arthur
Fighting/Steel for Lancelot
Dark/Steel for Mordred
Phycic/Steel for Merlin each of them would have their own specific item and signature move