Often, "magic" was inseparable from medicine and religion (including Christianity). A "healing spell" might include folk herbalism, the invocation of a spirit or saint, and other rituals.
The witch trials didn't take off until the very late Middle Ages into the Early Modern period, which is when European monarchies (including the Papacy) started consolidating power and began persecuting ALL kinds of nonconformists (including Jews, Christian minorities, gay people, etc).