I'm going to take a stab at this. First (as mentioned in Andres Caicedo's answer to this question), Siegel proved in 1972 that there is an algorithm to determine whether a quadratic equation in any number of variables has a solution, and so $(2,k)$ is decidable for any $k$.

Next, the case of $d = 3$ and $k = 2$ is decidable. The most interesting situation is the case of a curve of genus one, where Siegel proved that there are finitely many solutions, and Baker and Coates proved in 1970 (in a paper titled "Integer points on curves of genus $1$") that there is an effective algorithm to find them. I believe that $(1,k)$, $(2,k)$, $(3,2)$ and $(k,1)$ are the only cases now that are known to be decidable.

In particular, the case of $d = 4$ and $k = 2$ falls into the "unknown" category. The generic case here would be asking for the integral points on a plane quartic, and (unless the plane quartic is superelliptic), there is no straightforward way to apply Baker's linear forms in logarithms. The same issue arises for $d \geq 5$ and $k = 2$.

The next case is $d = 3$ and $k = 3$, which is definitely in the "unknown" category. (For example, it is unknown whether there are integer solutions to $a^{3} + b^{3} + c^{3} = 114$.) If the $d = 3$, $k = 3$ case were solvable even for homogeneous equations, we would be able to successfully do a $3$-descent on any elliptic curve over $\mathbb{Q}$ and hence there would be an algorithm to determine the ranks of elliptic curves (something else we don't know how to do).

Finding the boundary between "unknown" and "undecidable" is a bit tricky because most of the work on undecidable equations is for those where the variables are non-negative or positive, which is slightly easier. For example, Jones's 1982 paper mentioned in Caicedo's answer constructs a universal Diophantine equation with positive values for variables, with $9$ variables and degree $\approx 1.6 \cdot 10^{45}$. However, for integer values of variables, the best that is known
is Zhi Wei Sun's $11$ variable case (found in the 1992 paper "Reduction of unknowns in Diophantine representations"). In the positive integer case, there are unsolvable Diophantine equations with $4$ variables and with degree $58$, $8$ variables and degree $38$, $12$ variables and degree $32$, etc. I do not know of analogues of these results in the integer case.

Where is the boundary between unknown and undecidable? In Matijasevic and Robinson's 1975 paper where they prove the existence of a universal Diophantine equation with 13 variables, they say "We believe that the minimum number of unknowns necessary is less than $13$, possibly as small as $3$, but new methods will be needed to obtain the optimum result." I expect part of the reason that Matijasevic and Robinson believe the boundary may be $3$ is that they proved (in their joint 1974 paper in Russian) that given a polynomial $f(u,v,w,x)$ the problem of determining whether $\exists u, v \in \mathbb{N}$ so that $\forall w \in \mathbb{N}$, $\exists x \in \mathbb{N}$ so that $f(u,v,w,x) = 0$ is undecidable.

Note: The ABC conjecture may or may not be a theorem. If an effective version of the ABC Conjecture is true, there is (by a result of Elkies from 1981, "ABC implies Mordell") an algorithm for finding all rational points on curves, and this should give an algorithm for all the cases $(d,2)$ for any $d \geq 1$.