My cached thoughts start with a somewhat different question - not "what role does magic play in fantasy fiction?" (e.g. what fantasies does it fulfill), but rather... insofar as magic is a natural category, what does it denote? So I'm less interested in the relatively-expansive notion of "magic" sometimes seen in fiction (which includes e.g. alternate physics), and more interested in the pattern called "magic" which recurs among tons of real-world ancient cultures.
Claim (weakly held): the main natural category here is symbols changing the territory. Normally symbols represent the world, and changing the symbols just makes them not match the world anymore - it doesn't make the world do something different. But if the symbols are "magic", then changing the symbols changes the things they represent in the world. Canonical examples:
Wizard/shaman/etc draws magic symbols, speaks magic words, performs magic ritual, or even thinks magic thoughts, thereby causing something to happen in the world.
Messing with a voodoo doll messes with the person it represents.
"Sympathetic" magic, which explicitly uses symbols of things to influence those things.
Magic which turns emotional states into reality.
I would guess that most historical "magic" was of this type.
Ancient polytheism seems to basically go: the rituals are a deal or diplomatic ritual with powerful beings, and so they have a focus on orthopraxy (doing the thing) instead of orthodoxy (believing the thing). So does pouring wine on the dirt while reciting a nitpicky contract about how you formally request a good harvest from the Earth god count as symbols affecting reality? Technically yes, but I don't really feel like that's a good descriptuon of what's going on here, not in the way that it is for magic circles or spoken spells or voodoo dolls.
Fantasy depictions of alchemical rituals would be a counterexample if you were including fiction (because you take some stuff, do processes to change the stuff, and then you eat the stuff to change yourself, aka cooking/chemistry). Historical alchemy seems iffy (lots seems like "preparadigmatic chemistry and drug development", but they did use mystical reasoning).
A previous natural category attempt for magic, that I think I read Eliezer cite from someone else: the characterizing feature is that the ontologically basic elements are rather complicated, and often mentalistic, instead of the itsy bits of physics. I see this as coarser/more incomplete than yours.