It is always possible to construct a prime in the way described and the sequence is thus well-defined.

Let me first write out the process in more detail. For defining $a(n)$ we start with $p_n$ the $n$-th prime. Let it be $p_n=(d_{m-1} \dots d_0)_{10}$ where by the expression on the right I mean the decimal digit representation.

The numbers to consider then are $(d_{m-1}S_{m-1}d_{m-2} \dots d_2S_2d_1S_1d_0)_{10}$ where $S_i$ is a non-empty string of decimal digits.

The $a(n)$ is the smallest number of this form that is prime.
The question to answer is whether there is a prime of this form at all.
That we can/have to insert strings at several places is not very relevant.
We fix $S_2, \dots, S_{m-1}$ as $0$, or whatever string we like.

The fact we seek to prove will follow from the following; a subscript $g$-adic means a $g$-adic digit expansion.

**Lemma:** Let $g \ge 2$ be an integer, let $b_{k-1}, \dots , b_{0}, c_{l-1}, \dots, c_{0} \in \{0,\dots, g-1\}$, and let the $c_i$ be such that $(c_{l-1}\dots c_0)_g$ is co-prime to $g^l$. Then there is a prime, indeed infinitely many, of the form $(b_{k-1} \dots b_{0}Sc_{l-1}\dots c_0)$ where $S$ is a non-empty string over $\{0, \dots, g-1\}$.

To prove this we recall the following consequence of the Prime Number Theorem in arithmetic progressions (or the stronger Siegel–Walfisz theorem).

Let $c>0$ real. Let $n\ge 2 $ be a fixed natural number. For all sufficiently large $x$ coprime to $n$ the set $x+ i n$ with $0 \le i \le cx/n$ contains a prime number.

(The number of primes in the class of $x$ below $x$ is $\frac{1}{\varphi(n)}x/ \log (x) + O(x/(\log x)^2)$ while below $x+cx$ there are $\frac{1}{\varphi(n)}x(1+c)/ \log (x(1+c)) + O(x(1+c)/(\log x(1+c))^2 )= \frac{1+c}{\varphi(n)}x/ \log (x) + O(x/(\log x)^2 ) $, and for sufficiently large $x$ this means there need to be some in between.)

Now for the proof of our lemma. Let $N_o= (b_{k-1}\dots b_0)_g$ and $N_u= (b_{k-1}\dots b_0)_g$. We introduce a parameter $p$ to be fixed later. We note that the set of all numbers of the form $(b_{k-1} \dots b_{0}Sc_{l-1}\dots c_0)$ where $S$ is a string of size $p$ is $N_u + g^l i + g^{l+p}N_o$ for $0 \le i < g^p$.
We set $c= g^{-l-k-1}$. We set $x_p = N_u+ g^{l+p}N_o$ and we note $g^p> c x_p$. By assumption $N_u$ and thus $x_p$ is coprime to $g^l$. Thus if $x_p$ is sufficiently large there is a prime among $N_u + g^l i + g^{l+p}N_o$ for $0 \le i < g^p$. This can be attained by choosing $p$ large. This shows the lemma.

To finish the argument we apply the lemma with $d_0 = c_0$ and $b_{2i} = d_{i+1}$ and $b_{2i-1}=0$ for $i=1, \dots ,m$, for example (the choice of the $b_i$ is not really relevant). This is possible since $c_0=d_0$ is the lowest digit of a multi-digit prime and thus it is coprime to $10$.