In a metric space $M$:
If $A \subset M$ is complete and for each $\epsilon > 0$ there exists a compact $K \subset M$ with $A \subset \{ x \in M : d_M(x, K) \leq \epsilon \}$ then $A$ is compact.
Why is "$A$ is closed" not enough?
Edit: Is there a counterexample when $M$ is a normed vector space?
Since a compact metric space is complete, the completeness of $A$ is a necessary requirement.
If the ambient space $M$ is itself complete, then for subsets $A\subset M$ the two properties of being closed and of being complete coincide, so in that case you can replace "complete" with "closed".
If $M$ is not complete, you cannot replace "complete" with "closed".
The condition that for every $\varepsilon > 0$ there is a compact $K$ such that $A \subset B_\varepsilon(K)$ is another way of saying that $A$ is totally bounded, and a totally bounded metric space is compact if and only if it is complete. In a non-complete metric space, there are always closed but not complete totally bounded subsets, for example the underlying set of a non-convergent Cauchy sequence is closed and totally bounded, but not complete.