Short version: Consider a set of positive integers $\{m_i\}_{i=1}^n$ with $m_i < m_{i+1}$ and form an infinite binary sequence $s$ with $b$ $1$s and arbitrarily many $0$s subject to the following constraint: If there is a $0$ in position $j$, i.e., $s_j = 0$, then $s_{j+m_i} = 0$ for all $i$. It follows that $s_{j+M} = 0$ for any $M = \sum_i a_i m_i$, where the $a_i$ are non-negative integers. We can thus remove from the set any $m_i$ that is a multiple of some other $m_i'$. How many such sequences are there for fixed $b$ and $\{m_i\}$? (Feel free to only consider $n = 2$ if it helps.)
Medium version: The binary sequences described above are known as juggling states with $b$ balls, specifically those that are contained in juggling patterns of period $m_i$ for all $i$. For more on juggling states, see this paper.
Several properties of these states are quickly clear. We let $N(b)$ be the number of states with $b$ $1$s. All states start with either a $0$ or a $1$, so we can write $N(b) = N_1(b) + N_0(b)$. Any state with $b$ $1$s can be mapped to a state with $b+1$ $1$s by simply prepending a $1$ to the state, so it follows that $N_1(b) = N(b-1)$. We then find, for $b > 1$,
$$N_0(b) = N(b) – N(b-1).$$
Thus if we know $N(1)$ and $N_0(b)$ for all $b$, we can find $N(b)$. In general, letting $N_x(b)$ denote the number of states with some initial sequence $x$, we can use the same trick to show that $N_{1x}(b) = N_x(b-1)$, where by $1x$ we mean $x$ with a prepended $1$.
Setting $d = \gcd(m_1, \ldots, m_n)$, we can make some additional observations. If $d = 1$, $N_0(b)$ must be $0$ for sufficiently large $b$, and thus $N(b)$ must be eventually constant, since after the first $0$ there will be finitely many positions where the $b$ $1$s can be placed, as every sufficiently large positive integer is expressible in the form $\sum_i a_i m_i$. Thus when $b$ is sufficiently large, the only states that are found for $b+1$ are the same $N(b)$ states with an additional $1$ prepended.
For general $d$, letting $N_{0^k}(b)$ be the number of states with $b$ $1$s beginning with $k$ consecutive $0$s, we can prove that $N_{0^d}(b)$ is $0$ for sufficiently large $b$. (We let $k = 0$ represent $N(b)$.) In every case I have tried, I have found that for $k < d$, $N_{0^k}(b)$ is a polynomial of degree $d – k – 1$ for sufficiently large $b$, so $N(b)$ is eventually a polynomial of degree $d – 1$, but I am unable to prove this.
Long version: To phrase this more technically, we use the concept of a numerical semigroup (Wikipedia link), which is an infinite set of nonnegative integers containing $0$ that is closed under addition. Every element of a numerical semigroup $S$ can be written in the form $\sum_i a_i n_i$ for some finite set of non-negative integers $\{n_i\}$ with $\gcd(n_1, \ldots, n_r) = 1$, which are called the generators of $S$. We can then denote $S$ as $\langle n_1, \ldots, n_r\rangle$. The positive integers not contained in $S$ are called the gaps of $S$, and the number of gaps is denoted $g(S)$.
We see that for $d=1$, the positions of the zeros in the state, minus the position of the first $0$, form a numerical semigroup, specifically $S = \langle m_1, \ldots, m_n\rangle$. The gaps of $S$ are the possible positions for the $1$s after the first $0$. It follows that $N_0(b) = 1$ for $b = g(S)$, when all the gaps are filled, and $N_0(b) = 0$ for $b > g(S)$.
We can extend this to general $d$ by only looking at the positions of the $0$s, minus the position of the first $0$, that are congruent to $0$ modulo $d$. For example, for $\{m_i\} = \{4,10\}$, where $d = 2$, we see that the positions after the first $0$ where there must be additional $0$s are (4,8,10,12,14,…). Including $0$ to account for the first $0$, these values are the elements of the numerical semigroup $S = \langle 2,5 \rangle$ multiplied by 2. We see that $g(S) = 2$, corresponding to the positions 2 and 6. Thus if we have $0$s in positions $0$ and $1$, it follows that the state can only have $1$s in positions 2, 3, 6, and 7. Thus $N_{00}(b) = 1$ for $b = 4$ and $N_{00}(b) = 0$ for $b > 4$.
In general, we can use this numerical semigroup analysis to show that $N_{0^d}(b) = 1$ for $b = d \cdot g(S)$ and $N_{0^d}(b) = 0$ for $b > d \cdot g(S)$, where $S = \left\langle \frac{m_1}{d}, \ldots, \frac{m_n}{d}\right\rangle$. However, it is unclear how to work backwards from this point to show that $N(b)$ must eventually be a polynomial of degree $d – 1$.
One possible route would be to extend the identity $N_0(b) = N(b) – N(b–1)$ to states with more initial $0$s. Empirically, we find
$$ N_{0^{k+1}}(b) = N_{0^k}(b) – N_{0^k}(b-1)$$
for $0 \leq k \leq d–1$, but I have been unable to prove it. We can rewrite the right hand side as
$$\begin{align*}
N_{0^k}(b) – N_{0^k}(b-1)
&= N_{0^{k+1}}(b) + N_{0^k 1}(b) – N_{0^k}(b-1)\\
&= N_{0^{k+1}}(b) + N_{0^k 1}(b) – N_{10^k}(b),
\end{align*}$$
so it follows that proving the desired identity is equivalent to proving $N_{0^k 1}(b) = N_{10^k}(b)$ for $0 \leq k \leq d–1$, but I have been unable to do this either. In either form, this identity, combined with the already proven fact that $N_{0^d}(b)$ is eventually 0, would be sufficient to showing that $N(b)$ is a polynomial of degree $d-1$ for sufficiently large $b$, so any ideas would be helpful.
Best Answer
(Update: See below for characterizations of the $n=2$ case. In particular, this problem is apparently equivalent to counting certain integer partitions.)
Not a complete answer, but a sketch of some of the interesting aspects of this problem.
First I'll note that this problem is related to the money changing problem. The latter is known to be very hard for $n>2$, so we can expect the same in this case.
Polynomial behavior of $N(b)$ for large $b$.
As for the observation that $N_{0^k}(b)$ is a polynomial of degree $d-k-1$ for large $b$, we can prove this as follows. Consider residue classes mod $d$. For $j=0,\dots,d-1$, let $z(j)$ be the smallest integer such that $s_{j+z(j)d}=0$.
Lemma 1: There is an integer $M$ depending only on $\{m_i\}$ such that for all $p>M$ we have $s_{j+z(j)d + pd} = 0$. This follows from observations in the OP, or from known features of the money changing problem.
Hence there are only finitely many 1's in positions congruent to $j$ after position $j+z(j)$.
Lemma 2: $N(b) = \sum_{x=0}^b N_0(x)$.
Lemma 3: The number of ways to put $b$ 1's in positions congruent to $j$ is $N(b)$ for the reduced system $\{m_i/d\}_{i=1}^n$. Denote the counting function for this reduced system by $N'(b)$ to avoid confusion with the counting function for the original system.
Lemma 4: For $k<d$, $$ \begin{eqnarray} N_{0^k}(b) & = \sum_{x_0+x_1+\cdots +x_{d-1} = b} N'_0(x_0)N'_0(x_1)\cdots N'_0(x_{k-1})N'(x_k)N'(x_{k+1})\cdots N'(x_{d-1})\\ \end{eqnarray} $$
Combining with Lemma 2, we get $$ N_{0^k}(b) = \sum_{x_0+x_1+\cdots +x_{d-1} = b}\sum_{y_k=0}^{x_k} \dots \sum_{y_{d-1}=0}^{x_{d-1}} N'_0(x_0)N'_0(x_1)\cdots N'_0(x_{k-1})N'_0(y_k)N'_0(y_{k+1})\cdots N'_0(y_{d-1}) $$ The way to think about this is that the sum $x_0 + x_1 + \cdots + y_k + \cdots + y_{d-1}$ can be less than $b$ by some amount $r$, and the deficit $r$ can be separated into any of the $y_i$ summands. Thus, there are $d-k$ boxes to put $r=b-\sum_{i=0}^{k-1} x_i - \sum_{i=k}^{d-1} y_i$ objects into, and we can rewrite the previous expression as an unconstrained sum
$$ N_{0^k}(b) = \sum_{x_0,\cdots,x_{d-1}} \binom{b-\left(\sum_i x_i\right)+d-k-1}{d-k-1} N'_0(x_0)\cdots N'_0(x_{d-1}) $$ where the binomial coefficient counts the number of ways to put $b-\sum_i x_i$ objects in $d-k$ bins (take the binomial coeffients to be zero if the top number is negative). This is a polynomial in $b$ of degree $d-k-1$, as anticipated in the OP.
$N_0(b)$ for $n=2$.
The above observations reduce the problem to determining $N'_0(b)$. I'll specialize now to the $n=2$ case. It is known from the money changing problem (cf. Wilf, generatingfunctionology, 3.15.1) that for coprime $m_1, m_2$, the largest $b$ such that $N_0(b)\neq 0$ is $\frac{1}{2}(m_1-1)(m_2-1)$, and the final 1 is in position $(m_1-1)(m_2-1)-1$. The number $\kappa = (m_1-1)(m_2-1)$ is called the conductor of $\{m_1,m_2\}$. (I mention this just for notation and context--what follows probably can be understood with no knowledge of the money changing problem, though it may take some work on the reader's part.)
Consider the following bijection of the $\kappa/2$ positions where we can have a 1. Associate each such position with a lattice point in the Cartesian plane. For each $i=1,2,\dots,m_1-1$ and $j=1,\dots,\lfloor\frac{im_2}{m_1}\rfloor$, put the number $im_2-jm_1$ at lattice point $(i,j)$. The case of $m_1 = 5,m_2=7$ is shown below. The intuition of this is that we are partitioning the allowed 1 positions by congruence mod $m_1$, with each column one such equivalence class, arranged descending.
This creates a bijection between the allowed 1 positions and the positive lattice points lying below the line from $(0,0)$ to $(m_1,m_2)$. Note that moving right on this lattice corresponds to adding $m_2$ and moving down corresponds to adding $m_1$. Thus if we place a zero at some number, all the positions below and right (with equality allowed) on the lattice must also be zero.
Note that the labelled points form a Young diagram representing a partition of $\kappa/2$. The points also form a poset, ordered by $\alpha \leq \beta \iff $ $\beta$ is below and right of $\alpha$ (again with equality allowed).
From this characterization, it's easy to reformulate the original problem in several new ways: $N_0(\kappa/2 - x) = $
The reason that the argument is $\kappa/2-x$ is because we are now replacing 1's with 0's, starting from the maximum possible number of 1's (namely $\kappa/2$).
The last characterization in particular seems promising. For example, for $x<m_1$, the number of such partitions is unconstrained, and thus just equals the partition function $p(x)$. So in particular, we have $N_0(\kappa/2-x) = 1, 1, 2, 3, 5, 7, \dots$ up to $x=m_1-1$.
(I also wonder if Möbius inversion might be helpful here, but I haven't found a way to make it so yet...)
Since this problem apparently contains the problem of finding the partition function as a subproblem, it's not reasonable to look for a super compact closed form formula. However, it might be possible to find the generating function for $N_0(b)$. I do not know how to do this (presently), but I would say it would be totally worthwhile to post a new question asking that specifically. (It might be an appropriate question for Mathoverflow, as it seems reasonably sophisticated.)