When FindMinimum evaluates the first argument, k does not yet have a value so because of Plus threading we get
In[4]:= Norm[A.k - b]
Out[4]= Sqrt[Abs[-8 + {{1, 1}, {1, 2}, {1, 3}}.k]^2 + 2 Abs[-7 + {{1, 1}, {1, 2}, {1, 3}}.k]^2]
In[5]:= % /. k -> {0., 0.}
Out[5]= {12.7279, 12.7279, 12.7279}
which has the wrong dimensions. One could do, for example,
f[k_?VectorQ] := Norm[A.k - b];
FindMinimum[f[k], {k, {0, 0}}]
or
SetSystemOptions["EvaluateNumericalFunctionArgument" -> False];
FindMinimum[Norm[A.k - b], {k, {0, 0}}]
