Hardness of $k$-Plex
Lemma. If a graph has a $k$-plex on $m$ vertices, then it has a clique on $\frac m{k+1}$ vertices.

Proof. Greedily pick the vertices of the clique from the $k$-plex.

Since a clique on $m$ vertices is also a $k$-plex on $m$ vertices (for any $k$), we get that the size of the maximum $k$-plex is a $k$-approximation of the size of the maximum clique.
Since clique is hard to approximate with an $O(n^{1-\epsilon})$ factor, determining the largest $k$-plex is also hard for any $k=O(n^{1-\epsilon})$.