edit: I assume $c_n = 1$, as we have a minimal polynomial.
More like a long comment, not a complete answer: Set $c_k := 0$ for negative $k$ to simplify computations. Then we have (hoping I did no errors, as I calculated this by hand):
$$\theta^n = \sum_{k=0}^{n-1} -c_k\theta^k$$ $$\theta^{n+1} = \sum_{k=0}^{n-1} (c_{n-1}c_k - c_{k-1})\theta^k$$ $$\theta^{n+2} = \sum_{k=0}^{n-1} ((-c_{n-1}^2+c_{n-2})c_k + c_{n-1}c_{k-1}-c_{k-2})\theta^k$$ $$\theta^{n+3} = \sum_{k=0}^{n-1} ((c_{n-1}^3 - 2c_{n-1}c_{n-2} + c_{n-3})c_k + (-c_{n-1}^2+c_{n-2})c_{k-1}+ c_{n-1}c_{k-2}-c_{k-3})\theta^k$$
Thus, if we define a sequence of polynomials $p_i$ as $$p_0 = -1, \,\,\, p_1 = c_{n-1}, \,\,\, p_2 = -c_{n-1}^2+c_{n-2}, \,\,\,p_3 = c_{n-1}^3 - 2c_{n-1}c_{n-2}+c_{n-3}, \ldots$$ then I claim that $$\theta^{n+m} = \sum_{k=0}^{n-1} \left( \sum_{\ell = 0}^m p_{\ell} c_{k-m+\ell} \right)\theta^k.$$
Of course to prove this, one first needs to find and prove the structure of the $p_i$, but there seems to be a lot of structure in these polynomials to work with; e.g. there $c_{n-1}$ degree, the switching sign,...