The answer is $k=2$. If $a=1$, then $y_1=1$ is not prime. If $a=2$, then $y_1=3$ and $y_2=31$ are prime, while $y_3 = 2^{11}-1 = 23 \cdot 89$ is composite. It now remains only to check that $y_1, y_2$, and $y_3$ cannot all be prime for $a \ge 3$.

Suppose otherwise for the sake of contradiction that $y_1, y_2$, and $y_3$ are all prime. Because $y_i = 2^{x_i} - 1$, this implies that $x_1, x_2$, and $x_3$ are all prime; in particular, $a$ is prime. Observe that $x_2 \equiv 3 \pmod 4$, which implies that $x_3 \equiv 7 \pmod 8$. Therefore, we see that $2$ is a quadratic residue modulo $x_3$, so we may find some $s$ for which $2 \equiv s^2 \pmod{x_3}$. For this $s$, we have
$$2^{x_2} \equiv 2^{\frac{x_3-1}{2}} \equiv s^{x_3-1} \equiv 1 \pmod{x_3},$$
which implies that $x_3 \mid 2^{x_2} - 1$. But $y_2 = 2^{x_2} - 1$ is prime, so this implies that $2x_2 + 1 = x_3 = 2^{x_2} - 1$. We have also that $x_2 > 3$, which implies that $2^{x_2} - 1 > 2x_2 + 1$, yielding a contradiction.