Is $k$ fixed or not? Fixed means that $k$ is the same for every input, whether it's $3\times 3$ or $1000000\times 1000000$. If $k$ is fixed, then there are fewer than $n^k$ possible subsets so you get a deterministic polynomial-time algorithm just by trying each subset in turn.
On the other hand, if $k$ varies, either by being a part of the input or by being a function of $n$, then the problem is (probably) NP-complete. If it's part of the input, Yuval has shown NP-completeness by reduction from clique. If it's some function $f(n)$ and $f$ can be computed efficiently enough, you get NP-completeness roughly like this, again by reduction from clique.
We want to know if an $m$-vertex graph $G$ has a clique of size at least $k$. First, find some $k'\geq k$ such that $f(n)=k'$ for some $n\geq m$. Then, add $k'-k$ vertices to $G$ and make each one adjacent to every vertex in the new graph $G'$ (including the new vertices). Finally, add isolated vertices to $G'$ to give a graph $G''$ with $n$ vertices in total. (You'll need to deal with the case where $G'$ already has more than $n$ vertices!)
Now, $G$ has a $k$-clique if, and only if, $G'$ has a $k'$-clique if, and only if, $G''$ has a $k$-clique. But $k'=f(n)$ and the adjacency matrix of $G''$ is $n\times n$, so we can use Yuval's answer to determine if $G''$ has a $k'$-clique.