This is a slight elaboration on joro's comment; I was hoping that someone else would write a better version of this.
The integer points on $x^2-xy-y^2 = 1$ are precisely the pairs $(F_{2n+1}, F_{2n})$. So looking for solutions of the form $F_{2n+1} - F_{2m+1} = z^2$ is looking for integer points on $$ x_1^2 - x_1 y_1 - y_1^2 = x_2^2 - x_2 y_2 - y_2^2 = 1,\ x_1 -x_2 = z^2.$$ The other three possibilities give similar equations.
Each of these is a $K3$ surface. Here is where a better answer would review the major results on integer points on $K3$ surfaces. But I don't know them, so I'm going to stop here and hope someone else fills it in.