This is not an answer but a series of comments.
Here's an obstacle stopping you from straightforwardly generalizing the classical based on the Gaussian integers to, say, sums of two cubes. The problem is that $x^3 + y^3$ is not the norm of an element of a number field. If it were, the number field would be $\mathbb{Q}(\zeta_6)$, where $\zeta_6$ is a primitive sixth root of unity, but this is a quadratic number field and the norm of, say, $x + y \zeta_6$ is actually the quadratic factor $x^2 - xy + y^2$ of $x^3 + y^3$ rather than the whole thing.
The ring where norms give $x^3 + y^3$ is instead the ring $\mathbb{Q}[\zeta]/(\zeta^3 + 1)$, which unfortunately is not a field, so it's unclear in what sense the "algebraic integers" $\mathbb{Z}[\zeta]/(\zeta^3 + 1)$ inside it can have a reasonable theory of prime factorization. Moreover, the general element of this ring has the form $x + y \zeta + z \zeta^2$, with three parameters, and the corresponding norm is
$$x^3 + y^3 + z^3 - 3xyz$$
so even if one has understood this norm one still has to take into account the additional constraint that $z = 0$.
It's also worth pointing out that $m = x^3 + y^3$ describes a curve of genus $1$ for almost all values of $m$ and IIRC it's already unknown whether there exists an algorithm taking as input such a curve and determining whether it has an integer point or not. Bjorn Poonen has written about related topics; see, for example, this expository article.
Some other relevant stuff: