Why is Minimum $k$-cut NP hard when $k$ is specified as part of the input?
First, be careful what Vazirani actually says. On page 38, it is written that:


  "The minimum $k$-cut problem is polynomial time solvable for fixed $k$; however, it is NP-hard if $k$ is specified as part of the input."


(In particular, the claim you make about being NP-hard for any fixed $k \geq 3$ holds for a different problem, namely minimum weight multiway cut). Indeed, Wikipedia states this is the case as well: for any fixed $k$, you can solve the minimum $k$-cut problem in $O(n^{k^2})$ time. In other words, when $k$ is fixed, you have polynomially many ways of removing $k$ edges. So why does it matter if something is part of the input or fixed then?

When $k$ is fixed, it is not part of the input. The problem is this:


  (Minimum $k$-cut.) Input: A graph $G$. Question: Is there a $k$-cut?


So the problem is defined for every fixed value of $k$. We have minimum 2-cut, minimum 3-cut, minimum 4-cut, and so on. In contrast, the problem could be this:


  (Minimum cut.) Input: A graph $G$, an integer $k$. Question: Is there a $k$-cut?


Now, it is possible for $k$ to depend crucially on the size of the graph. This way a naive brute-force won't give you a polynomial time algorithm. Another example is given in this question of ours in the context of finding cliques.