You need 3 (blue) medals to upgrade one star on your main and all gold heroes. You need 2 medals on purple.

Each upgrade comes with a chance of failure and if you fail, you will lose a star. There are "safe" stages (4,7,9 and 10) where you won't lose a star on failure. After reaching 6 stars you will lose 2 stars on failure.