Is there a known complete formalization of solutions to $a^2 + b^2 = c^2 + k$ for a fixed constant $k>0$ similar to the one for primitive Pythagorean triples (i.e. $(a,b,c) = (m^2-n^2,2mn,m^2+n^2)$ )?
I saw on-line somewhere that Euler found all solutions to $a^2+b^2=c^2+d^2$ (I think it was $(a,b,c,d) = (xy-wz,xz+wy,xy+wz,xz-wy)$) so if $k$ is a square number $k=r^2$ we can find $x,y,w,z$ such that $xz-wy = r$. However, I was wondering if there is some known formulation having only two parameters (like we have for Pythagorean triples) given that $k$ is fixed.
I do not know of a solution to your first part unless $k-0$ if you want $k$ to be the same across the board. I also don't know about Euler finding all solutions to $a^2+b^2=c^2+d^2$ because there are an infinit number of them found most easily with deriviatives of Euclid's formula shown here as $$A=m^2-k^2,\quad B=2mk,\quad C=m^2+k^2\quad$$ By solving the C-function for k, we can find all triples with a given C by testing m-values to see which yield k-integers.
\begin{equation} C=m^2+k^2\implies k=\sqrt{C-m^2}\qquad\text{for}\qquad \bigg\lfloor\frac{ 1+\sqrt{2C-1}}{2}\bigg\rfloor \le m \le \lfloor\sqrt{C-1}\rfloor \end{equation} The lower limit ensures $m>k$ and the upper limit ensures $k\in\mathbb{N}$.
$$C=65\implies \bigg\lfloor\frac{ 1+\sqrt{130-1}}{2}\bigg\rfloor=6 \le m \le \lfloor\sqrt{65-1}\rfloor=8\quad\land \quad m\in\{7,8\}\Rightarrow k\in\{4,1\}\\$$ $$F(7,4)=(33,56,65)\qquad \qquad F(8,1)=(63,16,65) $$
Here we have $33^2+56^2=63^2+16^2$ and there are infinite numbers of these that can by found by testing C-candidates of the form where $C=4n+1$.