A partial answer: for fixed $m$, I provide a formula to compute a polynomial expression for $D_m(n)$ valid for all $n \geq m+1$. I'm not immediately sure if the expression will still be valid for $n < m+1$. This approach also works for a general polynomial in $j, k$, not just one of the form $(j-k)^m$.
Let $v$ be the all-ones vector, $J = vv^T$ the all-ones matrix, $D$ the diagonal matrix with diagonal entries $1, 2, \dots, n$, and $A = ((j-k)^m)_{1 \leq j, k \leq n}$, so we want to compute $\det(A + I)$. Note that for a given matrix $M = (m_{jk})_{1 \leq j, k \leq n}$, we have $DM = (jm_{jk})_{1 \leq j, k \leq n}$ and $MD = (km_{jk})_{1 \leq j, k \leq n}$, so it follows that $$A = \sum_{r=0}^m (-1)^{m-r} \binom{m}{r} D^r J D^{m-r}.$$
The matrix $T$ with columns $v, Dv, \dots, D^{n-1}v$ is a Vandermonde matrix with nonzero determinant, so these vectors form a basis. Consider the action of $A$ on this basis: we have $$AD^kv = \sum_{r=0}^m (-1)^{m-r} \binom{m}{r} D^r v v^T D^{m-r+k} v = \sum_{r=0}^m (-1)^{m-r} \binom{m}{r} s_{m-r+k}(n) D^r v$$ where $s_p(n) := \sum_{k=1}^n k^p = v^TD^p v$. Then if $B = (b_{jk})_{0 \leq j, k \leq n-1} = T^{-1}AT$ is the matrix of $A$ with respect to this basis (note the indices start at $0$), $$b_{jk} = \begin{cases} (-1)^{m-j} \binom{m}{j} s_{m-j+k}(n) & j \leq m \\ 0 & j > m \end{cases}$$ Now $\det(A+I) = \det(B+I)$, but since all entries of $B+I$ below the first $m+1$ rows are $0$ except the $1$'s on the diagonal, the determinant of $B+I$ is the same as the determinant of its upper-left $(m+1) \times (m+1)$ submatrix, so $$D_m(n) = \det\left((-1)^{m-j} \tbinom{m}{j} s_{m-j+k}(n) + \delta_{jk}\right)_{0 \leq j, k \leq m}.$$
Since each $s_p(n)$ is a polynomial in $n$ of degree $p+1$, and $m$ is constant, this gives an expression of $D_m(n)$ as a polynomial in $n$ (with rational coefficients), valid at least for all $n \geq m+1$. 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.