Hi!
We have decided to change the encoding, so that the encoding of the sitelink above would be /wiki/Category:Stuffed_animals. The encoding now should match how titles are encoded in Mediawiki codebase (non-ASCII characters that Mediawiki encodes will still be encoded as before).
Continuing the saga, the change now has been deployed on Wikidata. Which means, unfortunately, that for some time some entities (newly edited) would have the new encoding for sitelinks, and some (not edited recently) may still have the old encoding. As soon as the new dump will be produced (next Tuesday) we will begin reloading the servers, after which all the data will be using the new encoding, matching the encoding in Mediaiwki. I apologize in advance for the inconvenience that may be caused by having inconsistent data for a while (shouldn't be more than a week). I will make an announcement (hopefully the final one on the topic :) when it is all done.
Thanks,