Values for $a$ and $b$ as polynomials in $x,y$, when they exist, correspond to factorization of $\frac{x^p+y^2}{x+y}$ over the imaginary field $K_p:=\mathbb Q[\sqrt{-p}]$ of the form $$\frac{x^p+y^2}{x+y} = (a(x,y)+\sqrt{-p}b(x,y))\cdot (a(x,y)-\sqrt{-p}b(x,y)).$$ This Sage code factors $\frac{x^p+1}{x+1}$ over $K_p$ and tests if the result has the required form, in which case the (univariate) polynomials $a(x,1)$ and $b(x,1)$ are reported. As an example, it reports $a$ and $b$ for all primes below $100$. Each prime $\equiv 3\pmod4$ in that range happens to have a solution.
Example for $p=23$: $$a = (x + 1) \cdot (x^{10} - \frac{3}{2} x^{9} - x^{8} + 5 x^{7} - \frac{17}{2} x^{6} + \frac{21}{2} x^{5} - \frac{17}{2} x^{4} + 5 x^{3} - x^{2} - \frac{3}{2} x + 1),$$ $$b= \frac{1}{2} \cdot (x - 1) \cdot x \cdot (x^{8} + x^{5} - x^{4} + x^{3} + 1).$$