In fact, the maximum is achieved when no two of the 0's are in the same row or column, giving the maximum value $$ S=\sum_{i=0}^k (-1)^i {k\choose i}(n-i)!. $$ Proof. Suppose that there are two 0's in the same row, say the first. Then some row, say the second, has all 1's. Expand the permanent by the first two rows. One of the $2\times 2$ submatrices is $[0,0; 1,1]$. (I cannot figure out how to display a matrix in Math Overflow.) \pmatrix{0&0\cr1&1\cr}$. Changing this to $[1,0;0,1]$ \pmatrix{1&0\cr0&1\cr}$ does not decrease any of the $2\times 2$ submatrices from the first two rows, so the permanent of the entire matrix does not decrease. We can iterate this procedure (possibly using columns instead of rows) until no two 0's are in the same row and column, so the proof follows.
We now need to show that $S$ is at most $n!\left( 1 -\frac{k}{2n}\right)$. This is trivial for $k=1$, so assume $k>1$. By the Bonferroni inequalities (http://en.wikipedia.org/wiki/Boole's_inequality), $S$ is bounded by the first three terms, i.e., $$ S\leq n!-k(n-1)!+{k\choose 2}(n-2)! = n!\left(1-\frac kn+\frac{{k\choose 2}}{n(n-1)}\right). $$ Since $k\leq n$ we have $$ \frac{{k\choose 2}}{n(n-1)}\leq \frac{k}{2n}, $$ and the result follows.
