Here is a sketch of a proof. First I'll switch $q$ and $z$, since this is more consistent with standard "$q$-series'' notation. Then $A_k(n)$ is the constant term in $q$ of the coefficient of $z^k$ in 
$\prod_{j=-n}^n (1+q^jz)$.
We have
\begin{align*}
\prod_{j=-n}^n (1+q^jz) &=\exp\left(\sum_{j=-n}^n \log(1+q^jz)\right)\\
  &=\exp\left(\sum_{j=-n}^n \sum_{m=1}^\infty \frac{(-1)^{m-1}}{m} q^{jm}z^m\right)\\
  &=\exp\left(\sum_{m=1}^\infty (-1)^{m-1}\frac{z^m}{m} \frac{q^{m(n+1)}-q^{-mn}}{q^m-1}\right)
\end{align*}

So the coefficient of $z^k$ in $\prod_{j=-n}^n (1+q^jz)$ is a linear combination of products $p(m_1)p(m_2)\cdots p(m_r)$, where
$$p(m)= \frac{q^{m(n+1)}-q^{-mn}}{q^m-1}.$$
Thus the coefficient of $z^k$ in $\prod_{j=-n}^n (1+q^jz)$ is a Laurent polynomial in $q^n$ whose coefficients are rational functions of $q$.

Now let $G_k$ be the coefficient of $z^k$ in 
$$\sum_{n=0}^\infty \prod_{j=-n}^n (1+q^jz) t^n.$$
Then $G_k$ is a linear combination 
$$\sum_{m}\frac{R_m(q)}{1-tq^m},$$
where the sum is over a finite set of integers and $R_m(q)$ is a rational function of $q$. Expanding in partial fractions in $q$, we see that the constant term in $q$, which is $\sum_n A_k(n)t^n$, is a rational function of $t$, so $A_k(n)$ satisfies a linear recurrence with constant coefficients.

It is probably possibly to get a more explicit formula by expanding $\prod_{j=-n}^n (1+q^jz)$ by the $q$-binomial theorem.