Instead of pokéballs?

[Captain Barnacle]

Carry poffins around and they'll parade with you

 

[Dragalge]

I wish you could have just kept them out of their Pokeballs like in HG/SS, which would be more realistic, because they literally just transform into energy and fly into a red/white sphere.

Or maybe instead of trying to kill the Pokemon you could give it berries or something and see if it will befriend you or not?

 

[Nidoking76]

Maybe the Pokedex acts as a portal device that leads to Prof. Oak's lab, and the Pokemon there will go through the portal to you.

Just an idea, besides the obvious, well, to put it simply, just letting them walk beside you.