Magic fills a gap in our understanding of patterns
Humans (and probably any intelligent species) are hardwired to detect patterns. Not just in the moment (that silhouette looks like a tiger!) but also in time, linking a sequence of events together. It is an essential part of learning: Eat pink berries - feel sick, eat purple berries, feel good.
The problem is that we see patterns all the time where there really are none: I slaughtered a goat - the rains finally came. I can make the rain come by slaughtering a goat!
Most of these are unlearned when they are not repeatedly successful, but if other people hear of your pattern and have their own remembered patterns, they reinforce each other. With no way to explain how such a pattern actually works, we imagine it's "Magic".
A second aspect is that humans are also hardwired for social interactions, meaning we automatically infer other people's intentions and emotional state from their expressions and actions. This filter can also be triggered (wrongly) by other events and lead humans to imagine spirits and gods. Lightning struck Oona's hut at the top of the hill. Someone must be angry at her.
How to have humans without the concept of magic
Doing without pattern recognition is out of the question, as the humans would probably never have made it to the stone age development level. Having an advanced understanding of physical laws (as we do in the modern age) doesn't quite fit with the medieval theme.
"The Will of the Goddess" is actually quite useful to explain most patterns, but the danger is that humans apply human motivations to Gods (because we're hardwired to do that) and inconsistencies will lead to questions and then likely to the idea of other powers... and magic.
To have a satisfactory explanation for all the weird and inconsistent patterns humans see, an abstract concept works best. Karma is a good example, though because of it moralistic nature it would greatly change the nature of society.
The basic idea works though: Anything (good or bad) happening to you happens because of something in the (unknowable) past.
You can make up your own more neutral concept, say "Flow", inspired by water : It can keep your plants alive or wash away your village, it doesn't care. Whenever there is an obstacle to the flow, there will be eddies and swirls, which manifest in the form of all those patterns we perceive but don't understand. The critical part is that it is so abstract/inhuman/complex there is no way to influence it. Trying to change the Flow is like standing in the river pushing the water aside. It will simply flow around you or drag you under.
All together, people wouldn't need the concept of magic, since any pattern can be explained by either the will of the Goddess (if the event makes sense from our ideas of what She would do) or just "Flow" at work if it doesn't make sense.