Hmm ... let's see here.
Vero - Hmm ... perhaps Treecko. He seems like the type to have a more "badass" grass type, since grass types are often overlooked because of their numerous weaknesses.
Alice - While I do agree she'd most likely fit best with Fenniken, she could also work with a Snivy as well, but my vote goes for Fenniken.
Kuro - Mudkip. He looks like the type to use hard-hitting Pokémon like Swampert.
Lucia - Cyndaquil. Hard to explain, but Lucia is the more tom-boy-ish out of the two female Protagonists, who'd most likely use very powerful Pokémon by her side.
Ari - Bulbasaur. This was a hard one, as I can see any starter working for them, but I picked Bulbasaur, because they seems like the type to use something flower related, so Chikorita could work as well.
Decibel - Turtwig. They seem like a gentle and caring person, so it fits with Torterra, who lets smaller Pokémon live on it's little "island".