What is your definition of magic? Not all languages have a word that exactly corresponds to English "magic".
What if their language has "wizardry", "high knowledge", "prohibited knowledge", "sacred art", "unclean art" or something. What of these is magic?
Well. I suggest the following.
So,
First possibility, the most direct thing that can be defined as magical is something done by the force of thoughts, words, spells as opposed to done with hands.
Second possibility is the divine (or spiritual) inteventionintervention (by the god, spirits, ancestors, higher beings).
Third thing, is something related to life, consciousness and biology because living beings cannot be made by hands even now and there are philosophical issues with mind.
Fourth is anything done with hidden, secret knowledge (maybe obtained from gods or powerful ancients), even if by hands.
So given that, we say that various people can or cannot perceive a thing magical depending on their version of the origingorigin of the thing and their definitions.