Is the k-clique problem NP-complete?
Just elaborating what @Lamine pointed out : When $k$ is part of the input, $k$ can be as large as $\frac{n}{2}$, in which case the number of potential clique sets are $\binom{n}{\frac{n}{2}}$ which is at least $\left( \frac{n}{\frac{n}{2}} \right)^{\frac{n}{2}}$. Hence your naive algorithm would take time $2^{\frac{n}{2}}$ which is clearly exponential in input length $|x|+|k|=n+\log n$. The parameterized version $G(n,k)$ where we are looking for $k$-cliques in an $n$-vertex graph captures the hardness of the problem in its most generalized form because $k$ is part of the input. Hence a poly-time algorithm for $G(n,k)$ would also imply a poly-time algorithm for any specific $k$.