I'll assume all matrices are real. The equation is equivalent to $$ V^TAV = V^TXUU^TBV + V^TB^TUU^TX^TV $$ for every orthogonal $U,V$. In particular, you can take an SVD of $B$, so that $U^TBV=S$ is diagonal. After setting $M=V^TAV$ and $Y=V^TXU$, with $\|Y\|=\|X\|$, the equation reads $$ M = YS + SY^T. $$ This is now easy to solve entrywise: $$ m_{ij} = y_{ij}s_j + s_iy_{ji} \quad \forall i,j. $$ We can restrict to $i \leq j$, since both sides are symmetric, and solve in the least-squares sense these equations for each pair $(i,j)$ separately, since they are independent. Each is a $1\times 1$ or $2\times 1$ least-squares problem, which is easy to solve.

This idea should work also when $S$ and/or $A$ are singular, and produce a backward stable numerical method.

I'll assume all matrices are real. The equation is equivalent to $$ V^TAV = V^TXUU^TBV + V^TB^TUU^TX^TV $$ for every orthogonal $U,V$. In particular, you can take an SVD of $B$, so that $U^TBV=S$ is diagonal. After setting $M=V^TAV$ and $Y=V^TXU$, with $\|Y\|=\|X\|$, the equation reads $$ M = YS + SY^T. $$ This is now easy to solve entrywise: $$ m_{ij} = y_{ij}s_j + s_iy_{ji} \quad \forall i,j. $$ We can consider only the equations with $i \leq j$, since both sides are symmetric, and solve these equations in the least-squares sense for each pair $(i,j)$ separately, since they are independent. Each is a $1\times 1$ or $2\times 1$ least-squares problem, which is easy to solve.

This idea should work also when $S$ and/or $A$ are singular, and produce a backward stable numerical method.