Counterexample shown here for just adding edges:
If $k=5$, then you'd need another $3$ edges from each of the vertices in $\{5,6\}$. Because $5$ and $6$ already have edges to $11$ and $12$, all of those additional edges must be to vertices in $\{7,8,9,10\}$. But all vertices in $\{7,8,9,10\}$ already have degree $4$, and thus can only accept one edge each. That means that only a total of $4$ edges from $\{5,6\}$ can be accepted, leaving $2$ stubs on $\{5,6\}$ with no place to go.
It might still be possible to extend the graph if you add both edges and vertices, but I'm not sure how to systematically do that.
Incorrect old answer:
My original answer was incorrect as highlighted by Aryabhata's comment (unless you allow for weighted graphs or multigraphs), but I've left it below for reference.
Succinctly, yes. You've basically already answered the question.
I'll try to flesh it out a bit to make it more evident, but really I'm just repeating your own intuition:
Given a bipartite graph $G=(X,Y,E)$, $$ \sum_{x \in X} d(x) = \sum_{y \in Y} d(y) = |E| $$
since each edge counts towards the degrees of one vertex in both $X$ and $Y$.
We have assumed $G$ is balanced, so let $m \equiv |X| = |Y|$. Furthermore, we assume $k < m$.
Since $d(i) \le k, \forall i \in X \cup Y$, $|E| \le km$.
Case 1: $|E| = km$. Then $d(i) = k$, so done.
Case 2: $|E| < km$. Then for every vertex $i$, put $k - d(i)$ stubs on $i$ (recall that a stub is half of an edge, two stubs on different vertices can be joined to form an edge between those vertices, and that a stub counts towards the degree of a vertex).
Now, all vertices have degree $k$. However, we still need to join the stubs together to form edges to turn this back into a bipartite graph. Note that we added a total of $km - |E|$ stubs to vertices in $X$. Order them $\{s_1, ..., s_{km-|E|}\}$. Similarly, we can order the stubs in $Y$ as $\{t_1, ..., t_{km-|E|}\}$.
Then just join together $s_j$ and $t_j$ for $j \in [1,km-|E|]$, and you have your new regular balanced bipartite graph $G'$.
By a good coloring of a graph $G$ I mean a $2$-coloring of the edges with colors red and blue such that every vertex of degree at least $2$ is incident with a red edge and a blue edge.
Lemma. Let $G$ be a connected graph which is not an odd cycle. If $G$ has at most one vertex of degree different from $2$, then $G$ has a good coloring.
Proof. If all vertices of $G$ have degree $2$, then $G$ is an even cycle. If $G$ has just one vertex $v$ of degree different from $2$, then either $G=K_1$, or else $G$ consists of two or more cycles glued together at one vertex. (Note that $G$ is Eulerian, and consider the cycles traversed by an Euler circuit between successive visits to $v$.) In all these cases the existence of a good coloring is easily verified.
Theorem. Every connected graph which is not an odd cycle has a good coloring.
Proof. We use induction on the size of the graph, i.e., the number of edges. Let $G$ be a connected graph which is not an odd cycle, and assume that the theorem holds for all smaller graphs.
By the lemma, we may assume that $G$ has two distinct vertices, $u$ and $v$, whose degrees are different from $2$. Let $P$ be a path from $u$ to $v$. Color the edges of $P$ alternately red and blue.
Now consider the connected components of $G-E(P)$. Give each component which is not an odd cycle a good coloring, which exists by the inductive hypothesis. However, if any component $C$ of $G-E(P)$ is an odd cycle, then choose a vertex $w\in V(C)\cap V(P)$, and color the edges of $C$ alternately red and blue, except that the two edges incident with $w$ shall have the same color, and if $w$ happens to be an end vertex of $P$, that color shall be different from the color of the edge of $P$ which is incident with $w$.
It is easy to see that this is a good coloring of $G$.
Best Answer
You have to be allowed to add vertices. In that case it is provable by induction on the number of edges:
Assume G' := G \ e is a Subgraph of some Δ'-regular bipartite Graph K'.
1. Case Δ = Δ' + 1:
K = K' plus e plus an edge for every two other vertices.
2. Case e is in K':
K = K'
3. Case e is not in K':
Let e = (a,b). Because we do not increase Δ, there must be edges in K' \ G' f = (a,c) and g = (b,d). Make a copy of K' =: K'' and join them. Remove f, g and their copies. Connect e, the copy of e, (a,c'), (b,d'), (a',c), (b',d). Here a' is the copy of a etc.. This gives K with all the right edges and degrees.
We can start the induction at 0 edges, and take as K an edgeless bipartite Graph with partitions of the same size, so that it includes G.
Case 3 can done sometimes without the doubling of the graph, but not always. Your example is a case, which can be solved by doubling the graph. Adding vertices is also no problem for your point 1, because it is independent of the number of vertices.