Herby is probably correct (I only have 6 stars on anyone, vastly expensive and painful to fail past this point) but lets talk about spending gems for medals to star toons.

There are three places you can "buy" medals from. There is the purchase button on bottom right of stars panel, which costs you 10 gems per medal. This is a very bad investment. You can purchase them in the Fair. If I see them for 3 gems or less, I buy them. On Fridays I will spend up to 5gems since it gains you an extra medal on Saturday. You can purchase them in Labyrinth runs from one of the squares for 5 or 6 gems. Those typically are not worth buying unless it looks like you can get over 700 score by buying them, or maybe on a Friday for the extra Saturday.

Now, lets look at heroes. White heroes I don't even know if you can star, if you can, don't. Utter waste.

Blue heroes - Costs 1 medals per star. Some are better then others but you are not likely to be using them much later on in game (past lvl 50ish) and the stat increases are small enough that they wont make a huge difference in a fight. Some (ok, one) of the new blue heroes maybe useful in some line ups at a much higher level in the game, but at that point you can get gems for stars more easily anyways.

Purple heroes - Cost 2 medals per star. You might very well be using some of these even at very high levels in the game. Still, I would hesitate to put more then 3 stars on any of these fairly early. Getting Saffron or Ahmost Nehkbet a few stars earlier on and using them to tank is popular and not bad. Earlier on in the game the better defense runes aren't available so having some stat increases does help.

Gold heroes and Main Character - Cost 3 medals per star. Its always worth getting stars on you main character since they will always be in the line up. Rhize, Adamantine and Bloodstorm have been considered power hitters and most people star them up as high as they reasonably can. Shayd was very popular because of her ability to stun bosses and fairly high magic damage when she hit. Now, with her stun and hit rate decreased she is less popular in mid power level (8M+ until you get lightbringer sets). Smoulder generally isn't loved because of the general weakness of his attack, even though it has the potential to hit all opponents. Although with the large number of new mages that have recently been added, he might regain some favor. Dawnbringer is an upgraded Valla with a nice bonus to critical. I don't see him used much but he isn't bad. Most people prefer attacks that penetrate a row rather then hit an entire column.