How does the value of K determine number of local optima in NK model?
Let's take the opposite extreme, $K=0$, so that each site has an independent effect on fitness. Without loss of generality, we can say that at each locus $n$, the $1$ allele confers an advantage $s_n$ over the $0$ allele. Then there is just one local optimum, the global optimum, at $\vec{1}$, so $M_1=1$ (and $P_m=2^{-N}$).

The key difference is that in the $K=0$ case each fitness comparison of a focal genotype with a neighbor is independent of the rest: the fact that mutating the first gene decreases fitness, for instance, doesn't make it any more likely that mutating the second gene will decrease fitness. For any $K$, it is necessarily true that the focal genotype has a probability $1/(N+1)$ of being fitter than all of a set of $N$ other randomly chosen genotypes, but we're interested in comparing it to its neighbors, which are not a random selection, and are only equivalent to a random selection when $K=N-1$.