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'$.
The graph in your first question has no perfect matching. Since there are only $3$ vertices in $P_1$, a matching using all of those vertices can use at most $3$ of the $7$ vertices of $P_2$ and therefore cannot use all of them.
The two definitions are indeed of two different things. A perfect matching exhausts all of the vertices, so a bipartite graph that has a perfect matching must have the same number of vertices in each part. Deo is defining a directional notion: a complete matching from one part into the other. If $P_1$ and $P_2$ are the parts of a bipartite graph, $P_1$ had $m$ vertices, and $P_2$ has $n$ vertices, then a complete matching of $P_1$ into $P_2$ has $m$ edges, and a complete matching of $P_2$ into $P_1$ has $n$ edges. Thus, the former is possible only if $m\le n$, the latter is possible only if $n\le m$, and a perfect matching (which is automatically a complete matching of $P_1$ into $P_2$ and a complete matching of $P_2$ into $P_1$) is possible only if $m=n$.
Best Answer
Let $V = \{v_i\}_{1\leq i \leq n}$ and $W = \{w_j\}_{1\leq j \leq m}$ be sets of $n$ and $m$ vertices corresponding to each part. I will write $[\![s]\!]$ to refer to $\{1,\dots ,s\}$. Essentially, we can characterize each bipartite graph $G$ with a function
$$ \Gamma_G : [\![n]\!] \longrightarrow \mathcal{P}([\![m]\!]) \setminus \{\emptyset\} $$
such that $\Gamma_G(i) = \{j : w_j \in N(v_i)\}$. Note that from this we can also recover $N(w_j)$ for $w_j \in W$. Therefore, our problem reduces to counting the amount functions from $[\![n]\!]$ to $\mathcal{P'} := \mathcal{P}([\![m]\!]) \setminus \{\emptyset\}$ such that every vertex in $W$ has a neighbour, that is, $\cup_{i \in [\![n]\!]} \Gamma(i) = [\![m]\!]$. I will denote this set as
$$ \mathcal{F} = \{\Gamma \in (\mathcal{P}')^{[\![n]\!]} : \cup_{i \in [\![n]\!]} \Gamma(i) = [\![m]\!]\} $$
Since there are $(2^m -1)^n$ functions of the form $f : [\![n]\!] \to \mathcal{P}'$ in total, it would suffice to count $\mathcal{F}^c$ and substract it from $(2^m -1)^n$. Now, because
$$ \mathcal{F}^c = \bigcup_{j \in [\![m]\!]}\{\Gamma \in (\mathcal{P}')^{[\![n]\!]} : j \not \in \Gamma(i) \ (\forall i \in [\![n]\!])\} $$
we can count this set using the inclusion-exclusion principle:
$$ |\mathcal{F}^c| = \sum_{k = 1}^m(-1)^{k+1}\sum_{\emptyset \subsetneq S \subseteq [\![m]\!], |S| = k}|\bigcap_{s \in S}\{\Gamma \in (\mathcal{P}')^{[\![n]\!]} : s \not \in \Gamma(i) \ (\forall i \in [\![n]\!])\}| $$
More concisely,
$$ |\mathcal{F}^c| = \sum_{k = 1}^m(-1)^{k+1}\sum_{\emptyset \subsetneq S \subseteq [\![m]\!], |S| = k}|\{\Gamma \in (\mathcal{P}')^{[\![n]\!]} : S \cap \Gamma(i) = \emptyset \ (\forall i \in [\![n]\!])\}| $$
Let's count each set of the inner sum. If $S$ is a proper subset of $[\![m]\!]$, to give a function such that each image is disjoint with $S$ is the same as giving a function that maps each $i \in [\![n]\!]$ to a subset of $[\![m]\!] \setminus S$ (except the empty set which we have already excluded). Therefore, for each $i \in [\![n]\!]$ we have $2^{m-|S|}-1$ choices, giving a total of $(2^{m-|S|}-1)^n$. Thus,
$$ |\mathcal{F}^c| = \sum_{k = 1}^m(-1)^{k+1}\sum_{\emptyset \subsetneq S \subseteq [\![m]\!], |S| = k}(2^{m-|S|}-1)^n = \sum_{k = 1}^m(-1)^{k+1}{m\choose k}(2^{m-k}-1)^n $$
And finally,
$$ |\mathcal{F}| = |(\mathcal{P})^{[\![n]\!]} \setminus \mathcal{F}^c| = |(\mathcal{P})^{[\![n]\!]}| - |\mathcal{F}^c| = (2^m -1)^n - |\mathcal{F}^c| = \\=(2^m -1)^n + \sum_{k = 1}^m{m\choose k}(-1)^k(2^{m-k}-1)^n = \\ = \sum_{k = 0}^m{m\choose k}(-1)^k(2^{m-k}-1)^n = \sum_{k = 1}^m{m\choose k}(-1)^{m-k}(2^{k}-1)^n. $$