I claim that
$$\|(a_{i,j})\| \le n \left\|\sum_i a_{i,i}\right\|.$$
Indeed, the map
$$\operatorname{Tr}: M_n(A) \to A: (a_{i,j})\mapsto \sum_i a_{i,i}$$ is easily checked to be completely positive.
Let $\{u_i\}$ is an approximate unit for $A$. Then the matrices $$U_i:= \begin{pmatrix}u_i & 0 & \dots & 0\\ 0 & u_i & \dots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 &\dots & u_i\end{pmatrix} \in M_n(A)$$ determine an approximate unit for $M_n(A)$. By general properties of completely positive maps, $$\|\operatorname{Tr}\| = \lim_i \|\operatorname{Tr}(U_i)\| = \lim_i \|nu_i\| = n$$ and the desired inequality follows.