1 kill == 2 gems worth of upgrade progress
For a new hero, it costs 1000 gems to purchase an upgrade from level 1 to 2. Playing this champion for the first time and getting 100 kills will reduce this cost to 800.
This is easily testable:
Pick a hero that isn't level 3 yet.
Tap the upgrade button to see how many gems it will cost to upgrade to ...
Without rigorous testing or word from the developer, we'll never know.
Personally, it seems to act like a weighted random system. I've noticed that you really don't get more heroes than currentLevel+X, and if you have currentLevel-Y heroes, they spawn more frequently to help fill in your numbers.
The exact heroes you get, and the order you get them in, ...
To my knowledge, it's all random. However, before starting the next round you can add a hero to your party. It costs 1 token, and the button is in the bottom left hand corner of the screen before you start the next level.