Why is Clique NP-complete while k-Clique is in P for all k?
The polynomial depends on the parameter $k$. In particular, the algorithm that people have in mind runs in time $O(n^k)$ (better algorithms might exist, but I believe that we don't know a running time better than $O(n^{O(k)})$. The running time of your proposed algorithm is then big O of
$$
 \sum_{k=1}^n n^k,
$$
which is no longer polynomial.