A more or less mechanical approach is to work modulo $4$. Note that for any integer $k$, $k^2\equiv 0 \pmod{4}$ or $k^2\equiv 1\pmod{4}$.
So, modulo $4$, $x^2-y^2$ can only take on the values $0$, $1$, and $-1$.
More basic, and more useful, is to suppose that $x^2-y^2=n$. Then $(x-y)(x+y)=n$. Note that for any integers $x$ and $y$, the numbers $x-y$ and $x+y$ are both even or both odd. (If we want a proof, their difference $2y$ is even.)
In neither case is $(x-y)(x+y)$ twice an odd integer. You started along these lines. Note that you were one step from the end.
Remark: The reason the second idea is more useful is that when it comes to solving $x^2-y^2=n$, we express $n$ as a product $st$ of integers of the same parity, and solve the system $x-y=s$, $x+y=t$. The solution is $x=\frac{s+t}{2}$, $y=\frac{s-t}{2}$. If $n$ is twice an odd integer, then this process breaks down, because one of $s$ and $t$ will be odd and the other even, so we do not get integers $x$ and $y$.
Sorry, I can't think of a good hint to give you a push. Here is my solution. There likely is a better way of approaching it, since this is from Art and Craft.
Deal with the case $p=2$ separately. Henceforth, $p$ is an odd prime.
If $\gcd (x, y) = k > 1$, then $k^p \mid p^z$, which implies that $k \mid p^z$. Thus, we can divide out by $k$. Henceforth, assume that $\gcd(x,y) = 1$.
Since $x + y \mid x^p + y^p$, hence $ x+y = p^n$. We have
$$x^p + (p^n - x)^p = p^z.$$
With the condition that $\gcd(x,y) = 1$, we get that $ p \not \mid x$. As such, $p^{n+1}$ divides $x^p + (p^n - x)^p$ but $p^{n+2}$ doesn't. Hence,
$x^p + (p^n - x)^p = p^{n+1} $.
This becomes extremely restrictive. For $p \geq 5$, we have
$LHS \geq \frac{p^{5n}}{16} > p^{n+1}=RHS$,
Hence, the only possibility is $p=3$.
Best Answer
Rewrite it as a quadratic equation in $n$: $4n^2+3n -2^m+1 = 0\implies \triangle = 3^2-4(4)(1-2^m)= 9-16+16\cdot 2^m=2^{m+4}-7=k^2\implies k^2+7=2^{m+4} $. This problem has appeared in an article by author J.Cremona of Nottingham UK, and in that article, they proved that the only possible solutions are: $m + 4 = 3,4,5,7,15$. I leave this for you to finish.
Reference:
$1)$.https://www.researchgate.net/publication/266524000_On_the_Diophantine_equation_x_2_7y_m