Problem: developers don't want to add new legendary skills because they don't make money off of them, but many old heroes need these skills to become useful again. New heroes are constantly released because they can be monetized in contests.
Solution: put items required for the new legendary skill quests as contest rewards. ITEMS WILL ALSO BE AVAILABLE BY OTHER MEANS, which stops this from being p2w. This is just a way to unlock the skills faster.
Bonus: As further incentive, include a skin for the hero getting their legendary in the contest. This will make it extra tempting to push if you like the hero being featured.