Is Vertex Cover of size $k >100$ polynomial time solvable?
We don't actually iterate over subsets $V'$ of size $C$, because that would be running in time $\Theta (n^k)$.  While that is polynomial for fixed $k$, there is an algorithm that runs in time $O(2^k \cdot n)$, which is much better.
The problem you have stated is not really very well defined, so let's try to clear it up.
The Vertex Cover problem is given a graph $G$ and a number $k$ and asks whether there exists a vertex cover in $G$ of size at most $k$.  This problem is NP-complete (as long as $k$ is not a constant).
However, if you ask to find any vertex cover in $G$, then you can reply with $V(G)$, which has size $n$.  This version is of course polynomial time solvable and uninteresting.
The answer is therefore: Vertex Cover is NP-complete.  If you fix the bounds, however, you can solve the problem in time &quot;polynomial&quot; time (exponential in the bounds).