I tried all the main apps and nothing at all works satisfactorily.
Even ones that appear successful end up mismatching songs or replacing singles with album versions, live versions with singles, and explicit tracks with censored ones, so on.
In the end I devoted a few hours to manually rebuilding playlists myself. Not fun!
[As an aside, Apple really should make a tool for this. Surely there is a way to conduct audio fingerprinting on a Spotify track and come up with a match in the Apple Music library, a la iTunes Match. Though I suppose Spotify could just block an app like that from accessing the Spotify servers.]