For any p the e values is not lower bounded:
set say x=1, then x^2*(x^3+y^3)=y^3+1 goes to inf for y>inf.
For your 2nd question: about solving the equation for a given n=p+e:
x^2*(x^3+y^3)=n
first method: factorize n, then try each squared divisor as for d=x^2 you can solve it: y=(n/dx^3)^(1/3) ofcourse check if y is an integer or not (you had two choices for x: x=+sqrt(d)).
2nd method: economical solution, find only all p<10^9 that is a prime divisor of n (and then the exact primepower p^e divisor), after this again try the squared divisors, the idea of this approach is that for random(!) n values it is unlikely that there is even a single p value for that p^2n (you have less than 1e9 probability for this).
