Lyra is good and Sherazin is as well. Kalimos also seems nice but shaman seems weak compared to priest, paladin and rogue. That being said wickerflame isn't even a necessity for most paladin builds. Finja, Tirion and Lightlord should be your priorities there. All this to say it's what class you want to play the most that you should decide from. Not a poll responded too by strangers.
I don't play much priest so I don't have any insight on how good Lyra is. Kalimos and Wickerflame are interesting in that they're relatively common discovers off of cards that are already played in decks that could use them (Servant of Kalimos, and Stonehill Defender). Wickerflame has an easier substitute (Tar Creeper) than Kalimos does, so I'd place him on a slightly lower crafting priority. Sherazin seems really great if you like playing miracle-y Rogue decks. I don't have Sherazin but having to use cards to keep killing it feels bad and I think that speaks for something.
1/2: Sherazin or Kalimos depending on whether you'd prefer Garden/Miracle Rogue or Elemental Shaman 3: Wickerflame ???: Lyra
If you have Edvin I advise crafting Sherazin because Miracle is a relatively cheap deck and it brings a lot of fun. Aggro Paladin needs a lot of epics, Finja, Tarim and Tirion so it depends on your collection. Lyra is fun if you have Shadow Visions.
As a Paladin Main, I have to say that you need Wickerflame only for Control Paladin (and maybe Handbuff if you want to play that). The other Paladin decks use Sunkeeper. Kalimos is a good card, but Elemental Shaman is'nt a top tier deck right now and if you play Elemental Jade you can easily swap him out. Sherazin is nice for Miracle Rogue or even N'Zoth Tempo if you want to be creative. And if you play Priest a lot, you basically can't go around Lyra. She's an amazing Value card in combination with Radiant Elemenal, Shadow Visions and Elise the Trailblazer.
I've only played with this a little bit, It didn't overly impress me honestly, it's not strong enough to turn around a behind game, but not strong enough to insta-win either. It just seems like a bigger blaze caller.
This is what I voted for, I think that Sherazin is one of the more stronger mid-game legends, that has a few broken interactions with it (i.e N'zoth etc) that make it both fun to play, but also competitively strong.