Compute 'insertable' letters in a regular language
Edit: The OP changed the question. What follows works for one interpretation of the original question.

I'm assuming you are given a DFA $A = (Q,\Sigma,\delta,q_0,F)$. The method can be adapted to handle NFAs.

Let the word be $w = w_1 \ldots w_n$. For each $i \in \{0,\ldots,n\}$, calculate the state $s_i$ that the automaton reaches after reading the prefix of length $i$ of $w$. For each $i \in \{0,\ldots,n\}$ and each accepting state $q \in F$, calculate the state $t_{i,q}$ that the reverse automaton reaches when starting at $q$ and reading the reverse of the suffix of length $i$ of $w$. Let $T_i = \{ t_{i,q} : q \in Q \}$.

For each $i \in \{0,\ldots,n\}$ and each symbol $a \in \Sigma$, check whether $\delta(s_i,a) \in T_{n-i}$. If so, $a$ can be inserted at position $i$: $w_1 \ldots w_i a w_{i+1} \ldots w_n \in L(A)$.

The running time is $O(n(|\Sigma| + |Q|))$, and the method requires space $O(|Q|)$ (if implemented by going over $i = 0,\ldots,n$, in this order).