With an idea by Louis Jachiet, we managed to design a PTIME algorithm for this task. Long story short, it's a dynamic programming algorithm where you sort the $b$'s by decreasing "ending time" (i.e., by increasing $q_i$ above), consider the $b$'s by intervals of "starting time" (the $p_i$ above), and restrict the search to greedy schedulings that follow the idea for $(ab)^*$ given in the question. Somewhat surprisingly, the problem is in PTIME even if the target regular language is also given as part of the input (i.e., not fixed). Also, the algorithm would also work if, instead of copies of the letter $a$, we had a fixed word on some alphabet; however all the $b$'s should be the same symbol.
I'll rephrase the problem of my question to a problem where each $b$ comes with a pair $(s_i, e_i)$ saying that this $b$ must be inserted with at least $s_i$ $a$'s to the left, and strictly less than $e_i$ $a$'s to the left. This is equivalent to the original problem phrasing in the question (take $s_i := p_i$ and $e_i := m + 1 - q_i$ where $m$ is the number of $a$'s), but it is a bit easier to reason with: we can now see the constraints as defining an interval $[s_i, e_i[$ of positions where the insertion can take place. By a position $p$, I mean a position in the word of $a$, i.e., $0 \leq p \leq m$; when we insert multiple $b$'s then they do not change positions of other $b$'s in the word of $a$'s. Besides, since all $b$'s are the same symbol, it suffices to know the position where we insert them; we don't care about the relative positions of the $b$'s that are all inserted at the same position in the word of $a$'s.
I will need to talk about state pair sets of the automaton, which are just sets $S$ containing pairs $(q, q')$ of states. Given a word $w$ over $\{a, b\}$, I will write $\phi(w)$ for the state pair set that it achieves, i.e., all $(q, q')$ such that there is a path from $q$ to $q'$ labeled by $w$, which can clearly be computed in PTIME from $w$ and an automaton representation of the word. Given two state pair sets $S$ and $S'$, I define $S \odot S'$ to be the set of all state pairs $(q, q'')$ that can be obtained by combining a pair of $S$ and of $S'$, formally $S \odot S' = {(q, q'') \mid \exists q', (q, q') \in S \land (q', q'') \in S'}$. Notice that we have $\phi(w w') = (\phi(w)) \odot (\phi(w'))$ for any words $w$ and $w'$. What is more, the question of whether a word is accepted or not boils down to checking whether $\phi(w)$ contains a pair $(q_0, q_f)$ for a final state $q_f$. (What I'm redefining here is basically the transition monoid of the automaton, for those familiar with it.)
I will consider the $b$'s by decreasing ending time $e_i$, and break ties in some arbitrary but consistent way, so when I talk about the $i$-th $b$, with constraints $(s_i, e_i)$, then it is the $i$-th $b$ according to this order that I fixed.
Let me now claim that, if we can achieve a word $w$ by insertions of $b$'s into the $a$'s, then we can achieve the same word $w$ by doing insertions following a greedy strategy: when I insert the $i$-th $b$ at a position $p$ in the word of $a$'s, then all subsequent $b$'s that could also go at that position (i.e., $s_j \leq p < e_j$ for some $j$) are inserted to the left of that position, i.e., their position is $p'$ with $p' \leq p$. Let's see why we can always restrict to greedy strategies without loss of generality. Consider a stategy to do insertions to achieve $w$, and let's see that we can change it into a greedy strategy that achieves the same word. Consider a violation in the current strategy where we insert the $i$-th $b$ at position $p$ (so $p_i \leq p < e_i$) and the $j$-th $b$ (with $j > i$) could also go at that position (so $p_j \leq p < e_j$) but it was inserted to the right, i.e., $p' > p$. Let's see why the $i$-th $b$ can also be inserted at $p'$, which justifies that we can fix that violation by swapping the two insertions, and thus iteratively repair any strategy to a greedy strategy. By definition of the order, we have $e_j \leq e_i$, so as $p' < e_j$ we have $p' < e_i$. Now, as $p_i \leq p$ and $p < p'$, we have $p_i \leq p'$. So indeed $p \in [p_i, e_i[$ and we can indeed fix the violation by inserting the $i$-th $b$ at $p'$ and the $j$-th $b$ at $p$.
Now I can explain the dynamic algorithm. We will compute, for all $0 \leq i \leq j \leq m$, for all $0 \leq s \leq s' \leq m$, for all $0 \leq k \leq n$ (with $n$ the number of intervals), the set $S(i, j, s, s', k)$ which is the union of the state pair sets over all words that can be obtained by taking the subword of $a$'s from the $i$-th $a$ (included) to the $j$-th $a$ (excluded), performing insertions of $b$'s using exactly the $b$'s with position $i \geq k$ in the order (numbering them from $0$ to $n-1$) and with starting time $s \leq s_i < s'$, and considering the word obtained in this fashion (containing $j - i$ $a$'s and some $b$'s inserted before, after, or between them).
The quantity that we wish to compute to solve our problem is $S(0, m, 0, m, 0)$, telling us what can be achieved by inserting all intervals in the whole word of $m$ $a$'s; we then simply check if there is a pair of the form $(q_0, q_f)$ in the result, with $q_0$ the initial state and $q_f$ a final state.
The base case is the $S(i, j, s, s', n)$, where we ask what can be achieved without any insertions: this is simply the effect of the $a$'s on their own, formally, it is $\phi(a^{j-i})$.
Now, for the inductive step, consider $S(i, j, s, s', k)$ with $k < n$. Consider the $k$-th copy of $b$ and its interval $[s_k, e_k[$. If we don't have $s \leq s_k < s'$, then we are not considering this $b$, so we simply have $S(i, j, s, s', k) = S(i, j, s, s', k+1)$. Otherwise, we are considering the $k$-th $b$, and we claim that:
$$S(i, j, s, s', k) = \hspace{-1cm} \bigcup_{\max(i, s_k) \leq p \leq \min(j, e_k-1)}\hspace{-1cm} S(i, p+1, s, p+1, k+1) \odot \phi(b) \odot S(p+1, j, p+1, s', k+1).$$
In particular, if the interval for the $k$-th $b$ does not overlap with $[i, j[$, then $S(i, j, s, s', k) = \emptyset$ (meaning that we cannot perform the insertions).
To see why this formula holds, observe that we must insert the $k$-th $b$ as we are considering it, and this insertion must be at a position $p$ such that $s_k \leq p < e_k$, so $s_k \leq p \leq e_k-1$, and also we are considering insertions in the subword from the $i$-th $a$ (included) and the $j$-th $a$ (excluded) so $i \leq p \leq j$ (we can insert immediately after the end of this subword of $a$). Now, all remaining $b$'s (strictly after $k$) with starting position in $[s, s'[$ are partitioned between those with starting position in $[s, p+1[$ and those with starting position in $[p+1, s'[$. Let's argue that these $b$'s must be inserted as we claim, i.e., the first ones in the subword of $a$ between $i$ included and $p+1$ excluded (so at or before $p$) and the second ones between $p+1$ included and $j$ excluded (so strictly after $p$). For the second ones, this is clear, as their starting position is $\geq p+1$ so they must be inserted at position $p+1$ or later. For the first $b$'s, either their ending time is $\leq p+1$, in which case they must necessarily be inserted strictly before position $p+1$; or their ending time is $> p+1$, but in this case, as their starting position is $< p+1$, this means that they could legally be inserted at position $p$ where we inserted the $k$-th copy of $b$; now by definition of a greedy strategy, since they come after this $k$-th $b$ in the order which we inserted at a position $p$, then they must be inserted at a position $\leq p$.
Formally, correctness can be shown by showing inductively that the $S(i, j, s, s', k)$ contains the right state pair set: one direction is because what we compute really corresponds to a way to perform the insertions; the other is because any way to perform the insertions is equivalent to a greedy strategy, and all greedy strategies are represented by the above reasoning.
This algorithm clearly establishes that the problem is in PTIME, with complexity like $O(n \times n^4 \times m \times \mathrm{Poly}(A))$ where $A$ is the automaton. We're not claiming that this is optimal. :)
