Yes, it can always be done, while having a $k$-regular simple graph at every step. This is a result of Roger Eggleton from the 1970s which is closely related to earlier work of Hakimi for multigraphs and Ryser for 0-1 matrices.[1] A later result of Richard Taylor is that if the first and last graphs are connected then you can arrange for all the intermediate graphs to be connected too.[2] Richard also showed the same for 2-connectivity.[3]  All these results hold for arbitrary degree sequences and not just regular graphs.

Usually the operation is called "switching".  It is actually pretty useless for generation as there is no way to efficiently tell if you have seen a graph before. It is useful for other things though; for example you can turn it into a Markov chain to make random graphs.

[1] R.B. Eggleton, Graphic sequences and graphic polynomials: a report, in Infinite and Finite Sets, Vol. l, ed. A. Hajnal et al, Colloq. Math. Soc. J. Bolyai 10, (North Holland, Amsterdam, 1975), 385-392.

[2] R. Taylor, Constrained switchings in graphs. Combinatorial mathematics, VIII (Geelong, 1980), pp. 314–336, Lecture Notes in Math., 884, Springer, Berlin-New York, 1981.

[3] R. Taylor, Switchings constrained to 2-connectivity in simple graphs. 
SIAM J. Algebraic Discrete Methods 3 (1982), no. 1, 114–121.