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\|.$$