Criteria of compactness of an operator

Yes, $K$ is compact.

Note first that we can assume that $K$ is selfadjoint; indeed, if $K$ satisfies the hypothesis, so do $K^*$ and $K\pm K^*$, and if we prove that the real and the imaginary parts of $K$ are compact, then we have that $K$ is compact.

Using the Weyl-von Neumann-Berg Theorem (II.4.1 or II.4.2 in Davidson's C$^*$-algebras by example) we can write $$ K=A+T, $$ where $A$ is selfadjoint and diagonal in some basis; and $T$ is compact. Being compact, $T$ satisfies the hypothesis and so $A=K-T$ does too. Now, since $A$ is diagonal, the hypothesis implies that its diagonal tends to zero, and so it is compact. Then $K$ is compact, being a sum of compacts.

To finish, note that it is essential that the property of small entries of $K$ holds for any basis. If we fix a single basis, it is possible to have operators $K$ satisfying $\langle Ke_i,e_j\rangle\to0$ (in the sense of the question) but not compact. Indeed, let $$ K=\bigoplus_n\begin{bmatrix}1/n&\cdots&1/n\\ \vdots&\ddots&\vdots\\ 1/n&\cdots&1/n\end{bmatrix}. $$ This is an orthogonal sum of pairwise orthogonal projections, so it is an infinite-dimensional projection, thus not compact.