For $m\geq n$, let $A^{m, n}$ be the $m\times m$ matrix given by
$$
A^{m, n}_{i, j} =
\left\{\matrix{
0, & \text{if } i, j\leq n, \cr
\langle e_i, Ae_j\rangle , & \text{otherwise}.
}
\right.
$$
For example,
$$
A^{3,2} =
\pmatrix{
0 & 0 &\langle e_1, Ae_3\rangle \cr
0 & 0 &\langle e_2, Ae_3\rangle \cr
\langle e_3, Ae_1\rangle & \langle e_3, Ae_2\rangle & \langle e_3, Ae_3\rangle
}.
$$
Theorem. The operator $A$ is compact if and only if $\lim_{m,n\to\infty} \|A^{m, n}\| =0$.
Proof. Let $P_n$ be the orthogonal projection onto the span of the first $n$ basis vectors and notice that, for
$m\geq n$, the
matrix of
$$
P_mAP_m - P_nAP_n
$$
coincides with $A^{m,n}$ inside the top left $m\times m$ block of entries, and has
zero entries everywhere else. It follows that
$$
\|A^{m, n}\| = \| P_mAP_m - P_nAP_n\|,
$$
so the condition regarding the limit in the statement is equivalent to $\{P_nAP_n\}_n$ being a Cauchy
sequence.
As we are working within the space of bounded operators on a Hilbert space, which is complete, we may replace
"Cauchy" by "converging" in the sentence above.
Assuming that this condition is true, that is, that $P_nAP_n$ converges, then the limit operator has the same matrix as
$A$ (I'm assuming we are using Physicist's inner-product, which is conjugate linear in the first variable), and hence
coincides with $A$. In other words
$$
\lim_nP_nAP_n = A.
$$
Since $P_nAP_n$ is finite rank, hence compact, and since the space of compact operators is closed, it
follows that $A$ is compact. This proves the "if" part. As for the "only if" part, suppose that $A$ is compact. Using
that $\{P_n\}_n$ is uniformly bounded and converges to the identity operator in the strong (pointwise) topology one shows
that
$P_nAP_n$ converges to $A$ in norm, so $\{P_nAP_n\}_n$ is a Cauchy sequence which we have already agreed to be
equivalent to the condition in the statement.
Remarks:
Since $A^{m, n}$ is a finite matrix, its norm is (in principle) computable in terms of the $\langle e_i, Ae_j\rangle $, as
required.
Computing norms of finite matrices is a hard numerical problem, so this criterion might not be as useful as the OP would like.