Is this part correct:
$$(\Delta^2+\Delta -2)^{-1} =\left( -2\left(I-\frac{\Delta^2+\Delta}{2}\right)\right)^{-1}=-\frac{1}{2} \left(I+\frac{\Delta^2+\Delta}{2}+\left(\frac{\Delta^2+\Delta}{2}\right)^2+\ldots+\left(\frac{\Delta^2+\Delta}{2}\right)^n+\ldots\right)$$
Let $L = \Delta^2+\Delta -2$. Note that this operator maps polynomials into polynomials, moreover $\deg \left(L \circ p_d(n)\right) \leqslant d$.
Hence we can search for the inverse among polynomials in $n$ of degree 3, and you can use the method of indeterminate coefficients.
Note that $$\Delta_n \binom{n}{k} = \binom{n}{k-1}$$ and that $$ n^3 + 1 = 6 \binom{n}{3} + 6 \binom{n}{2} + \binom{n}{1} + \binom{n}{0} $$ Suppose $p(n) = L^{-1} \circ \left(n^3+1\right)$, and write as $$ p(n) = \sum_{k=0}^{3} a_k \binom{n}{3-k} $$ and now $$ L \circ p(n) = \left(-2 a_0 \right) \binom{n}{3} + \left(a_0 - 2 a_1\right) \binom{n}{2} + \left(a_0 + a_1 - 2 a_2\right) \binom{n}{1} + \left(a_1 + a_2 - 2 a_3\right) \binom{n}{0} $$ Equating the above to $n^3+1$ and solving for indetermined coefficients gets us $$ a_0 = -3, a_1 = -\frac{9}{2}, a_2 = -\frac{17}{4}, a_3 = -\frac{39}{8} $$