You are solving an underdetermined system but expecting integer solutions so I guess what you want is to pose this as a diophantine problem. I don't know how to do this from Julia but using SymPy directly (in Python) there is a function diophantine for this kind of problem e.g.:
In [3]: diophantine(x**2 + y**2 - 25, [x, y])
Out[3]: {(-5, 0), (-4, -3), (-4, 3), (-3, -4), (-3, 4), (0, -5), (0, 5), (3, -4), (3, 4), (4, -3), (4, 3), (5, 0)}
It doesn't look like your example is implemented though:
In [4]: diophantine(x**2 + y**3 - 31)
---------------------------------------------------------------------------
NotImplementedError: No solver has been written for cubic_thue.