Edited to give a more complete (and cleaner) answer valid for all $m, n$. My original answer only applied for $n \geq m+1$, and only went through the proof for the case of $(x-y)^m$.
Say we have a polynomial $P(x, y) = \sum_{0 \leq a, b \leq m} c_{ab} x^a y^b$, and want to compute $\det(A + I)$ as a function of $n$, for $A = A(n) = (P(j, k))_{1 \leq j, k \leq n}$. Let $C = (c_{ab})_{0 \leq a, b \leq m}$, and let $V$ be the $n \times (m+1)$ matrix with columns $v_0, v_1, \dots, v_m$, where $v_d$ is the vector with $j$-th entry $j^d$ for $1 \leq j \leq n$. Then $v_a v_b^T$ is the $n \times n$ matrix with $(j, k)$-entry $j^a k^b$, so it follows that $$A = \sum_{0 \leq a, b \leq m} c_{ab} v_a v_b^T = VCV^T$$ and thus by the Weinstein-Aronszajn identity $$\det(A + I) = \det(VCV^T + I) = \det(CV^TV + I) = \det(CS + I),$$ where $S = V^T V$. Note that $C$, $S$, and hence also $CS+I$ are $(m+1) \times (m+1)$.
Now, for $0 \leq a, b \leq m$, the $(a, b)$-entry of $S$ is $v_a^T v_b = s_{a+b}(n)$, where $s_d(n) := \sum_{j=1}^n j^d$. Since each $s_d(n)$ can be expressed as a polynomial in $n$ of degree $d+1$ (with rational coefficients), all entries of $CS+I$ are fixed polynomials in $n$, and thus the equation above expresses $\det(A+I)$ as a polynomial in $n$ (with rational coefficients when all $c_{ab}$ are rational).
In the case of $P(x, y) = (x-y)^m$, the resulting formula is $$D_m(n) = \det\left((-1)^{m-a} \tbinom{m}{a} s_{m-a+b}(n) + \delta_{ab}\right)_{0 \leq a, b \leq m}.$$ In this case, the degree of each term in the expansion of the determinant is $(m+1)^2$, so $D_m(n)$ has degree at most $(m+1)^2$. The calculated polynomial agrees with yours for $m=1$ and $m=2$, I haven't checked $m=3$ yet.