Don't know if it counts, but nearly all books by Walter Moers have some kind of animal (or better creatures) as a protagonist. I just roughly translate the books, only know the german names:
Captain Bluebear: Of course a bear (and yes, he is blue)
Rumo: A Wolpertinger (a creature half dog half deer)
The City of lost books: A Lindwurm (like a humanoid dragon)
Der Schrecksenmeister (sorry, this is nearly untranslatable. Something like "witchmaster" grasps maybe the meaning) : A cat (or better a magical type called "crat")
More or less fantasy books.
Another one that maybe is far stretched: The Metamorphosis by Franz Kafka.
Not the protagonist but the most famous animal crime case: The murders in the rue morgue by Edgar Allan Poe.
Also not mentioned: The whole genre of the fable. Animal stories from the antique to today. Of course this are allegories, but still with animals.
The most famous bear of all time: Winnie-the-Pooh (does it count?)
I better stop now or I will just go on and on
