Magic spells as ambient nanotech that's poorly understood and difficult to invoke -- hence the "Vancian" system which comes from Jack Vance's "Dying Earth" series.
Magic items as remnant tech.
Different "races" as the vast gulf of time has led to speciation.
Gods as posthuman or artificially intelligent entities that have transcended the world but still keep an eye on it from time to time.
And so forth. There's literally nothing medieval about it, but it could be 1,000,000 AD. Just think of their medical technologies in light of our era's!
(All assuming, of course, that it's "baseline reality" and not a sandbox, as it was in Neal Stephenson's The Fall.)