Why can you find a $k$-clique in polynomial time, but determining if there is a $k$-clique is NP-complete? You can find a $k$-clique in $n^k$ time by examining all possible sets of vertices of size $k$.  So why is it NP-complete to determine if there is a clique of size greater than $k$?  It looks like you can solve it in polynomial time if $k$ is a constant.
Indeed we could resolve the $k$-clique problem for fixed $k$ by inspecting $\binom{n}{k}$ subgraphs.  However, the number $k$ is considered an input to the problem too.


  In the $k$-clique problem, the input is an undirected graph and a number $k$, and the output is a clique of size $k$ if one exists (or, sometimes, all cliques of size $k$). -- Wikipedia


If e.g. $k=\lfloor n/2 \rfloor$, then $\binom{n}{k}$ increases exponentially (not polynomially) with the input size.
I think finding a k-clique is simply O(m+n). If we know k, we can store a list of all the nodes which have a degree of atleast k-1. Then for every node in that list, we check if all of its neighbors or atleast n-1 of its neighbors (depending on whether degree of the node is n-1 or > n-1) have degree n-1 or not. Using adjacency lists, this step takes O(m+n). So total complexity is O(m+n). It's linear.