As Will notes, this does not really work for odd $n \gt 1$ as the determinant of $M$ is not a square. On the other hand, if $n$ is even then the determinant of $M$ is a square.
Note that your solution to $A^2=M$ for $n=2$ has $A$ symmetric and thus is also a solution of $AA^t=M$. I think $AA^t=M$ is the more promising equation to generalize.
In either version, when $n=2m$, the determinant of $A$ would have to be $(x_1^2+x_2^2+\cdots +x_n^2)^m.$ It is hard to imagine this happening without the entries of $A$ all being of the form $\pm x_i.$ That is the only case I will consider.
I don't think there is a solution to $A^2=M$ for $n=4.$ However, $$A=\begin{pmatrix} x_1 & x_2 &x_3 &x_4\\ x_2 & -x_1 &x_4 & -x_3 \\ x_4 &x_3&-x_2&-x_1\\ x_3&-x_4&-x_1&x_2 \end{pmatrix}$$ does give $AA^t=M.$
If all the $x_i$ are set equal to $1$ then $A$ would become a matrix with entries $\pm 1$ such that $A^2=nI_n$ or $AA^t=nI_n$, depending on which version one is trying to solve. In the $AA^t$ case one would have a Hadamard matrix which means that $n=1,2$ or a multiple of $4.$
I suppose having entries of the form $\zeta x_i$ with $\zeta$ a root of unity could also be worth considering. In that case it would be natural to look at the conjugate transpose (which is, of course, just the transpose for real matrices) or perhaps $A^2=M$ where $A^t$ is the conjugate of $A.$
Later
I should say that I don't think there are any solutions for $n=4$ to $A^2=M$ , of the type I mentioned. I didn't look for one with entries of the form $\frac{x_1 \pm x_2 \pm x_3 \pm x_4}{2}.$ That seems promising. Of the type I mentioned (over $\mathbb{Z}$) one can see that $A$ would have to be symmetric and one can assume that the first row and column are $x_1\ x_2\ x_3\ x_4.$ This forces the second row and column to be $x_2\ -x_1\ \pm x_4\ \mp x_3.$ There are a few ways to finish off the remaining four entries and none worked. If $Q=A_4(x_1,x-2,x_3,x_4)$ is the matrix I gave, then I might expect a solution for $n=8$ of the form $$A=\begin{pmatrix} Q & R\\ S &T \end{pmatrix}$$
Where $R=S=A_4(x_5,x_6,x_7,x_8)$ and $T=-Q$ or $-Q^t$. That would give the right sign pattern. I did not get that to work. Note that we can shuffle the rows and multiply any of them by $-1$ without affecting $AA^t=M.$ All that matters is that distinct rows are orthogonal. And we never want to get a term of $\pm x_i^2$ as an off diagonal term in $M.$ Hence each $x_i$ should appear once in each row or column and we can assume that the first row and column are $x_1\ x_2\ \cdots x_8.$ So I suppose I could swap rows $3$ and $4$ in my solution for $n=4.$