It seems the answer is no, $E(G)$ can fail to be finitely presented even if $G$ is finitely presented.
I claim that a counterexample is given by $G=F_2\times F_2$.
First, as @SeanEberhard explains in the comments, $E(F_2\times F_2)$ is isomorphic to the subgroup $H$ of $F_3\times F_3$ generated by $\{(x,1),(y,1),(1,x),(1,y),(z,z)\}$, where $\{x,y,z\}$ is a generating set for $F_3$. Now I claim that $H$ is not finitely presented.
First I claim that $H$ contains the commutator subgroup of $F_3\times F_3$. Any simple commutator in $F_3\times F_3$ is an ordered pair of simple commutators in $F_3$, so it suffices to show that any $(g,1)$ for $g$ a simple commutator in $F_3$ lies in $H$ (and by a parallel argument also $(1,g)$). This is easy to see because given any word in $(x,1),(y,1),(z,1)$ (and their inverses) representing an element of $[F_3,F_3]\times\{1\}$, we can replace each instance of $(z,1)$ with $(z,z)$ (and $(z^{-1},1)$ with $(z^{-1},z^{-1})$) and get a word representing the same element of $[F_3,F_3]\times\{1\}$ but now lying in $H$.
Now that we know $H$ contains the commutator subgroup, we can use the Bieri-Neumann-Strebel-Renz invariant $\Sigma^2(F_3\times F_3)$ to conclude that $H$ is not finitely presented. Indeed, $H$ lies in the kernel of the homomorphism $\chi\colon F_3\times F_3 \to \mathbb{Z}$ sending $(z,1)$ to $1$, $(1,z)$ to $-1$, and all of $(x,1),(y,1),(1,x),(1,y)$ to $0$ (I guess it actually equals this kernel), and the computation of $\Sigma^2(F_3\times F_3)$ (see, e.g., Bux-Gonzalez) reveals that $[\chi]$ is not in $\Sigma^2(F_3\times F_3)$, since the "dead" edge from $(x,1)$ to $(1,x)$ in the defining flag complex has empty "living link". (Actually, I think $\Sigma^2(F_3\times F_3)$ is empty, so probably we didn't even need to isolate a particular $\chi$, and in fact every infinite index subgroup of $F_3\times F_3$ containing the commutator subgroup fails to be finitely presented, but I'll just leave this analysis as-is.)
Edit: By request and for the sake of being self-contained, here is the proof that $E(F_2\times F_2)\cong H$, compiled from @SeanEberhard's comments. Here $\{x,y,z\}$ is a free basis of $F_3$ and $H$ is the subgroup of $F_3\times F_3$ generated by $\{(x,1),(y,1),(1,x),(1,y),(z,z)\}$.
Let $\{a,b\}$ be a free basis of $F_2$. We have an epimorphism $\phi\colon F_3\to E(F_2)$ given by sending $x$ to $c_a$, $y$ to $c_b$, and $z$ to $id_{F_2}$, and we claim it is injective (hence an isomorphism). Indeed, given any non-empty reduced word in $c_a$, $c_b$, and $id_{F_2}$ (and their inverses) representing an element $f$ of $E(F_2)$, since $F_2$ is mixed identity-free, we can evaluate $f$ at some element of $F_2$ to get a non-trivial element of $F_2$, which means $f$ is a non-trivial element of $E(F_2)$. Hence $F_3 \cong E(F_2)$. This also shows $F_3\times F_3 \cong E(F_2)\times E(F_2)$. Let us identify $H$ with its isomorphic image in $E(F_2)\times E(F_2)$, generated by $\{(c_a,c_1),(c_b,c_1),(c_1,c_a),(c_1,c_b),(id_{F_2},id_{F_2})\}$.
Now consider the monomorphism $\psi \colon F_2^{F_2} \times F_2^{F_2} \to (F_2\times F_2)^{F_2\times F_2}$ given by sending $(f,g)$ to the function $f\times g$ defined by $(f\times g)(w,v):=(f(w),g(v))$. The restriction of $\psi$ to the subgroup $H$ is an isomorphism onto its image, which is generated by $c_{(a,1)}$, $c_{(b,1)}$, $c_{(1,a)}$, $c_{(1,b)}$, and $id_{F_2\times F_2}$, hence is $E(F_2\times F_2)$ as desired.
Best Answer
The answer is $K=2k$, which is an exercise. Here is a sketch: Let $f\colon \langle x_i\rangle\to G$ be a surjective homomorphism, and $h\colon \langle x_i\rangle*\langle y\rangle\to G$ the map defined by $h(x_i)=f(x_i)$, $h(y)=e$. Let $g\in G$ be arbitrary, and choose $w\in\langle x_i\rangle$ such that $f(w)=g$. Let $\alpha$ be the automorphism of $\langle x_i\rangle*\langle y\rangle$ which maps $y$ to $yw$ and leaves the other generators alone. Then $h(\alpha(y))=g$. Do this $k$ times, one for each element of your second generating tuple, then reverse the process, swapping the roles of the $x$ and $y$.
$K=2k-1$ doesn't suffice, by Kapovich and Weidmann, who in "Nielsen equivalence in a class of random groups" construct small-cancellation examples.