Minimize $ \arg \min_{A} {\| A x - b \|}_{2} $ (Least Squares Minimization on the Matrix)

Yes. Expanding the sum we get

$$\begin{align*}\sum_i \|Ax_i-b_i\|^2 &= \sum_i \sum_j (Ax_i-b_i)_j^2\\ &= \sum_i \sum_j \left(\sum_k A_{jk}x_{ki} - b_{ji}\right)^2\\ &= \sum_i \sum_j \left(\sum_k x^T_{ik} A^T_{kj} - b^T_{ij}\right)^2\\ &= \sum_i \sum_j (x^T A^T_j - b^T_j)_i^2\\ &= \sum_j \|x^T A^T_j - b_j^T\|^2. \end{align*}$$

So you can solve the problem using regular least squares; your matrix $x^T$ has rows equal to your original known vectors $x_i$, the unknown vector $A_j^T$ is the $j$th row of $A$, and $b_1^T$ is the vector containing all of the first entries of the $b_i$, etc.

For the second problem, note $$\frac{\rm d}{\rm{d} A}((Ax-b)^TC^{-1}(Ax-b))=-2xb^T{C^{-1}}^T+{C^{-1}}^TAxx^T+C^{-1}Axx^T$$ so if $C^{-1}$ is symmetric (hence $C$ is also symmetric), we have the normal equation for $\sum_i(Ax_i-b_i)^TC^{-1}(Ax_i-b_i)$ $$\sum_iAx_ix_i^T=\sum_iCx_ib_i^TC^{-1}$$ or $$\sum_ix_ix_i^TA^T=\sum_iC^{-1}b_ix_i^TC$$

So $A$ can be computed row by row, and let $a_j$ be the $j$-th column of $A^T$ ($j$-th row of $A$) and $d_j$ be the $j$-th column of $\sum_iC^{-1}b_ix_i^TC$, thus $a_j$ can be computed by solving $$\sum_ix_ix_i^Ta_j=d_j$$