I've always been a fan of fairy tales where the main character's kindness to animals helps him or her become the hero of the story.
The Queen Bee, by the Brothers Grimm is a good example. Baba Yaga and the Girl With the Kind Heart is another. Sometimes the main character is even mighty, and displays the wisdom of having humility even when one is rich and powerful, such as the legend of King Solomon and the Bee. You'll notice that the Solomon story has a similar motif as that of "The Queen Bee."
Those are some of my favorite stories in which compassion toward animals (and in the case of Baba Yaga, toward things too!) is rewarded. What are yours?