Indeed, for every pair (n,m) in your domain (m+6 at most 3n) there is a planar graph on n vertices with m edges: take a path of n-2 vertices, and add an edge from each vertex to each of two additional vertices u and v. Add the edge u,v, and now take away enough edges from this planar graph to get down to m edges. Any of your non planar graphs can be rewired to one of these selected planar graphs this way.
(As an aside, it might be of interest to rewire while preserving degree sequence. I suggest searching for that as well.)
Using the large example above, take w to be one of the n-2 vertices, and rewire all the path edges to turn w into the center of a star with all the other (n-3) path vertices connected to w. We now have degree of u,v,and w each at n-1, and all the remaining path vertices have degree 3. I conjecture that this example will need almost if not exactly a third of its edges rewired to become planar, and that it will be a significant challenge to find a graph needing proportionately more rewiring.
On the other hand (assuming the graph is connected, as having more components probably makes the rewiring easier) one can choose a spanning tree of the original graph and preserve that and just rewire other edges. Thus at least 1/3 of the edges can be kept. One can extend this slightly to have a spanning bonsai, which is like a spanning tree but with additional edges that do not cross, and thus preserve a little more of the graph. I am not sure how to find a large spanning bonsai in a connected graph.
In the above, I am assuming that I can freely remove and replace edges at will. J.C. gently reminds me that a sequence is involved where the start and final edge of a move share a vertex. I outline an argument that shows every replacement removal can be implemented by a few of these rewirings.
So we want to remove an edge (a,b) and install edge (c,d). If the four named vertices are really three, this is just a rewiring. If one of the four pairs ac ad bc bd does not exist, this is accomplished by two rewirings. If disaster befalls us and those four edges are taken, we rewire one of them to cd, and then rewire ab to the removed edge. I think this is about as clean a proof sketch as one can get. So I reassert my previous claim that all graphs can be rewired to one of the graphs at the start of this post. I leave the formalization to others.
Gerhard "Graph Theory, Meet Topological Gardening" Paseman, 2018.05.08.