This answer arose by a discussion with @JamieGabe in the comments.

One can prove that
the map
$$\Phi: M_n(A) \to M_n(A): A \mapsto n \operatorname{Diag}(A)-A$$
is completely positive [Paulsen, "Completely bounded maps and operator spaces", exercise 3.6].

In particular, it is positive. Hence, writing $A= (a_{i,j})$ as in the OP, we obtain
$$A \le n \operatorname{Diag}(A)$$ 
and taking norms leads to
$$\|A\| \le n \lVert\operatorname{Diag}(A)\rVert=n \max_{i=1}^n \|a_{i,i}\| \le n \left\|\sum_{i=1}^n a_{i,i}\right\|.$$