A matrix $A$ is diagonalizable over the field of complex numbers if all eigenvalues of $A$ are distinct. To see this consider the Jordan decomposition $A = VJV^{-1}$, where $J$ is a complex matrix in the Jordan form. If all eigenvalues of $A$ are distinct, then $J$ contains only blocks of size $1\times 1$, hence $J$ is diagonal.
In order to compute a perturbation, that makex $A$ diagonalizable consider the complex Schur factorization of $A$, i.e. $A = UTU'$, where $U$ is unitary and $T$ is upper triangular with complex entries, and $U'$ denotes conjugate transposition. Diagonal of $T$ contains eigenvalues of $A$.
Let $\tilde{A} = U(T+D)U'$, where $D$ is a diagonal matrix, such that all diagonal elements of $T+D$ are distinct and $\|D\|_2\leq \mu$ for some $0 < \mu \leq 1$. Such matrix can be easlily constructed. Then $\tilde{A} = A + UDU'\equiv A + P$, and $\|P\|_2 = \|D\|_2 \leq \mu$. The matrix $\tilde{A}$ is diagonalizable.
For any two matrices $X$, $Y$ and any matrix norm:
$$\|e^{X+Y} - e^X\| \leq \|Y\|e^{\|X\|}e^{\|Y\|}$$
Thus
$$\|e^{A+P} - e^A\|_2 \leq \|P\|_2e^{\|A\|_2}e^{\|P\|_2} \leq \mu e^{\|A\|_2}e^{\mu} \leq \mu e^{\|A\|_2 + 1}$$
If we take $\mu = \min(1,\epsilon / e^{\|A\|_2 + 1})$, then $\|e^{A+P} - e^A\|_2\leq \epsilon$.
For a real matrix $A$ containing complex eigenvalues it is not possible to find a small perturbation $P$, such that $A + P$ is diagonalizable over the field of real numbers, but it is possible if $A$ has only real eigenvalues. Then, this construction can be repeated using the real Schur factorization.