Edit This answer only deals with self-adjoint matrices, and therefore does not address the current form of question.
The answer depends on the norm you are considering. The answer is no for the operator norm and self-adjoint matrices (see the references in the question Are almost commuting hermitian matrices close to commuting matrices (in the 2-norm)? and details below), but the answer is yes for the Hilbert-Schmidt norm (at least if you replace $O(\varepsilon)$ by $o(1)$, see the answers to the question). I do not know a counterexample for unitary matrices.
Here are some details on the counterexample for self-adjoint matrices. By Lin's theorem, if you consider self-adjoint matrices of norm less than $1$, the assumption that two of them approximately commute in the operator norm is equivalent to the assumption that two of them can be approximated in the operator norm by commuting matrices. A positive answer to your question for self-adjoint matrices therefore implies a positive answer to this question for the operator norm. Voiculescu showed that this question has a negative answer for $k\geq 3$, but it seems that the link I gave is not correct. See for example the references in the paper by Exel and Loring given in the comments.