In Star Trek (I assume you are broadly familiar with this franchise), manipulating spacetime is common, some species doing it better than other. Within the context of the franchise, it is not supernatural, but mundane.It was certainly supernatural.
True, but these beings live outside of space-time, they don't just manipulate it. I mean, to me, even in the Ster Trek universe that is beyond natural.
We've seen plenty of races that appear to exist outside of normal space time i.e. the Q.
According to merriam-webster dictionary the definition of deus ex machina ... just kidding. the def states: a person or thing (as in fiction or drama) that appears or is introduced suddenly and unexpectedly and provides a contrived solution to an apparently insoluble difficulty . So "that appears OR is introduced suddenly" the wormhole aliens appear suddenly to Sisko without his asking and change the hopeless situation for the crew, DS9 and the Alpha Quadrant.
As has been pointed out, the Wormhole liens have been in from the very first episode of the series which also demonstrated their ability to manipulate the wormhole. As for the wormhole aliens appearing without asking haven't we seen that before as well? So nothing really new that we hadn't seen before just reuse of things that had already been established.