Similarly, shouldn't we be just as perplexed about how physical entities interact with one another as we are about how mental states arise from brain states?
We are! We are just as perplexed about how physical entities interact. We spend over a billion dollars every year throwing protons around in the Large Hadron Collider because we're so perplexed as to how all this stuff really works!
As it turns out, understanding how the world works is quite the interesting and complicated philosophical problem. As for the mind body problem, consider how you can "know" that the mind is actually just a brain state? The first step in doing so is to describe what it means for a "brain state" to "know" anything. That's actually harder to do than it seems at first. When most people try to deal with this particular problem, their first few attempts either prove that "they know they don't know anything," which can be an infuriating paradox, or they accidentally prove that "a rock might know the meaning of life," which is equally infuriating in another way. Penning down the meaning of this has been the subject of millennia of philosophers.
I get the feeling that a lot of the confusion surrounding mind-stuff arises from centuries long training of rational people to reject certain non-physical absurdities, such as ghosts, fairies, magic, etc....
One has to be careful with arguments like this. There are other non-physical absurdities, like self, morals, marriage, etc, which are valued highly by many people. If one is not careful, one accidentally banishes these along with the ghosts and fairies. Keeping the non-physical that you want while discarding the non-physical that you do not turns out to be a challenge that keeps cultures going. One of the tools that has been used to explain this is the separation of mind and body. If your mind is subject to different rules than your body, then it's easy to explain why the rules you use to make sense of the physical world don't apply to the non-physical. If you do not use such a tool, then you must use more difficult approaches.
Myself, I find the most important part of making sense of mind/body is abduction: the inference rule that assumes the most likely hypothesis is true. It's an inference rule alongside deduction and induction which gets a lot less press, but it's important here. Someone who argues that there is only body, and mind supervenes on the body, typically argues so along the lines of abduction: "physics has explained so much of reality, it is likely that it explains all of reality." Some people are comfortable with this inference, others are not. Part of it is because, while science is making tremendous leaps and bounds into understanding the brain, we still don't even have a scientific definition for consciousness which meets the needs of the philosophical community, much less an agreement that that definition is the only possible right definition.
I, myself, prefer to take a compatabalist stance, and argue that both models fit the data. The real answer, if one even exists, is an unknown. We, as a species, have many tools for dealing with the unknown. Physics is only one of them. Maybe it's not the most effective way to approach all questions. Maybe the "best" way to view the universe hasn't even been developed yet? Why limit our search?