Firstly, let me make it clear that I am not saying that only humans have a theory of mind, and I am also not saying that it is a binary property, either you have it in full or not at all.
Having said that, one can still consider when, where, how and how often it evolved. For example, there are many species that cache food. Some (some squirrels and also scrub jays, for example) will either only pretend to cache the food they are carrying, or move it later, if they notice they are being observed. Is that an application of a general theory of mind at work, or an instinct that evolved for one particular circumstance? As far as the ethical treatment of animals is concerned, I have no objection to assuming the former, but if we want a scientific understanding of what is really going on, that assumption cannot be made without further evidence.
What you are overlooking, I think, is that there are several possible explanations for the externally-observable behavior, and once you recognize that, there should be no paradox. In our case, we, as privileged observers of our own minds, can see our theory of mind at work, and, through language, we can talk to other people and ask how it seems to them. Neither of these lines of inquiry are an option when it comes to studying other species.
There is an interesting parallel in ethics: some people are well-behaved because they are fearful of punishment or ostracism, while some do so out of respect for other people. You can't always tell motive from actions alone.