Hearthpwn

Here's my Secret Barnes Anyfin Paladin deck.

The game plan is to play stuff on curve, until you hit Anyfin Can Happen on Turn 10 to finish your opponent off.

The purpose of having 8+ secrets and 2 Mysterious Challenger is to act as pseudo-draw and deck filter so you can dig into your combo faster. You also don't want other minions in your deck that aren't essential to assembling your combo, so stuff like Doomsayer and Keeper of Uldaman are out. You want Barnes to hit a Murloc 5 out of X times. The fewer your other minions are, the better the chances for Barnes to summon a murloc. 

In order to guarantee that your 1st Anyfin Can Happen is lethal, you need to have 7 murlocs die from turns 1 to 9.

You only have 5 murlocs so you need to Redemption 2 of them anytime before Turn 10 to get the full 7 with Anyfin. Barnes fits perfectly for this purpose. The best choice to Redemption is Old Murkeye because he buffs himself and has charge. 2nd best target is Murloc Warleader, then Bluegill Warrior.

Mulligan:

Keep Secretkeeper and Murlocs. Keep Barnes if you have the coin.
It's ok to keep Mysterious Challenger against slower decks.

Edit: Updated with Karahzan cards. Barnes is Murloc #6.
Edit: Updated with Mean Streets cards. Finja for more dick filtering.

3/27/2017 Edits:
I don't want to Redemption the Noble Sacrifice 2/1 token. So I cut it.
I put in Getaway Kodo because I want more ways to duplicate my Murlocs. Getaway Kodo creates a copy of the minion in your hand, so the Murloc still counts as having "died" for Anyfin to resurrect later.
I am experimenting with cutting Muster for Battle because I don't want low value 1/1 minions being duplicated by Redemption o Getaway Kodo.
As suggested by MomoSpark from Reddit, I added 1 beast and 1 dragon to get more value out of Curator.

Cut Ivory  Knight. Although the deck can use the healing, and I like the possibility of if giving me an extra Anyfin or board clears, I want Barnes to summon a murloc 5 out of 9 times.

Flex spots: Coghammer, 2nd White Knight.
Can be swapped to Tirion Fordring who is a good target for Barnes and Redemption or Shielded Minibot for a stronger early game.
It might be ok to have 1 Truesilver Champion.
2 Solemn Vigil for more card draw is also welcome and will fill out the curve at 5.

4/7/2017 edit:
I cut the Curator package. Added Secretkeeper back in, along with the new 2/2 minion that discovers a secret.