For the first question: If $\vec a=(a_1,\ldots,a_n)$ and $\vec b=(b_1,\ldots,b_n)$, we need to find the image of every basis vector $\vec e_i$. For $\vec e_1$, you can pick any $j$ with $b_j=a_1$ and then map $\vec e_1\mapsto \vec e_j$ (i.e., $M\vec e_1=\vec e_j$, i.e., the $(j,1)$ entry of $M$ is $1$, or the value of the desired permutation $\pi$ evaluated at $1$ is $\pi(1)=j$). Continue with this method, but avoid repetition, i.e., when looking for $M\vec e_i$, pick any $j$ with $b_j=a_i$, but only among those indices you haven't picked yet.
For the second question: We mainly have to decide which value in $\vec a$ to associate with which value in $\vec b$. And then, in case of repeated values on either side, their corresponding indices may be permuted at will. First let us find one such association that is optimal.
Claim. If permutation $\pi$ minimizes $f(\pi):=\sum_i(a_i-b_{\pi(i)})^2$, then there exists a permutation $\sigma$ such that $$\tag1a_{\sigma(1)}\le a_{\sigma(2)}\le\ldots\le a_{\sigma(n)}$$ and $$\tag2b_{\pi(\sigma(1))}\le b_{\pi(\sigma(2))}\le\ldots\le a_{\pi(\sigma(n))}$$
Proof. There are certainly sorting permutaions $\sigma$ that guarantee $(1)$. But for each such $\sigma$, there may exist indices $\ell$ with $b_{\pi(\sigma(\ell))}>b_{\pi(\sigma(\ell+1))}$ (whereas of course $a_{\sigma(\ell)}\ge a_{\sigma(\ell+1)}$).
Among all $\sigma$ with $(1)$, consider one that minimzes the number of such bad indices $\ell$. If no suc $\ell $ exists, w are done. So assume otherwise.
Let $j=\sigma(\ell)$, $k=\sigma(\ell+1)$, $\pi'=\pi\circ (j\;k)$. Then
$$\begin{align} f(\pi')-f(\pi)&=(a_j-b_{\pi'(j)})^2+(a_k-b_{\pi'(k)})^2-(a_j-b_{\pi(j)})^2-(a_k-b_{\pi(k)})^2\\
&=(a_j-b_{\pi(k)})^2+(a_k-b_{\pi(j)})^2-(a_j-b_{\pi(j)})^2-(a_k-b_{\pi(k)})^2\\
&=-2a_jb_{\pi(k)}-2a_kb_{\pi(j)}+2a_jb_{\pi(j)}+2a_kb_{\pi(k)}\\
&=2(a_j-a_k)(b_{\pi(j)}-b_{\pi(k)})\\
&\le 0\end{align}$$
with equality iff $a_j=a_k$. By minimality of $f(\pi)$, we conclude that $a_j=a_k$. But them $\sigma':=(j\;k)\circ \sigma$ is a permutation that sorts $\vec a$ and has one less bad index than $\sigma$, contradicting our choice of $\sigma$. Hence the claim follows. $\square$
Now to find all optimal permutatons, you may permute arbitrarily among indices where components of $\vec a$ are the same, or similarly for components of $\vec b$. Note that considering only permutations among the components of $\vec a$ or only permutations among the components of $\vec b$ will not necessarily give you all optimal solutions. On the other hand, permuting both with $ßvec a$ and within $\vec b$ may count some solutions repeatedly, namely when ranges of equal value "overlap" in the sorted order of the components of $\vec a$ resp $\vec b$.