Why k- Vertex Cover is not in PTIME when it can be expressed in FO-logic
Your argument shows that for each fixed $k$, the problem $k$-VC can be solved in polynomial time (indeed, the algorithm enumerates all sets of size $k$ and checks whether they are vertex covers, all of which can be accomplished in $O(n^{k+1})$ or so). However, the vertex cover problem is different – it accepts $k$ as an input. This version of the vertex cover problem cannot be expressed in first-order logic.