The sharp upper bound is $2^n-2^{n-k}$. This can obviously be achieved, by a single monomial of degree $k$. To show it is an upper bound, we prove by induction on $n$ that if $p$ is a nonzero multilinear polynomial in $n$ variables of degree $\leq k$, then $p$ has at most $2^n-2^{n-k}$ zeroes. The base case $n=0$ is trivial.
Now suppose we know the upper bound is correct for polynomials in $n-1$ variables, and let $p$ be a nonzero multilinear polynomial of degree $\leq k$ in $X_1,\dots,X_n$. We can write $$p=X_nq+r,$$ where $q$ and $r$ are polynomials in $X_1,\dots,X_{n-1}$, and $\deg q\leq k-1$ and $\deg r\leq k$. Suppose first that $r=0$. Then $q\neq 0$, so by the induction hypothesis $q$ has at most $2^{n-1}-2^{n-k}$ zeroes. For $p$ to be zero, we must have either $X_n=0$ ($2^{n-1}$ solutions) or $X_n=1$ and $q=0$ (at most $2^{n-1}-2^{n-k}$ solutions). So $p$ has at most $2^{n-1}+2^{n-1}-2^{n-k}=2^n-2^{n-k}$ zeroes.
Now suppose $q+r=0$. Then $r\neq 0$, and moreover $q+r=0$ implies $r$ has degree at most $k-1$. So, by the induction hypothesis $r$ has at most $2^{n-1}-2^{n-k}$ zeroes. As in the previous case, we now see that $p$ has at most $2^{n-1}+2^{n-1}-2^{n-k}=2^n-2^{n-k}$ zeroes (the first term corresponding to the case $X_n=1$ and the second two terms corresponding to the case $X_n=0$).
Finally, suppose $r$ and $q+r$ are both nonzero. Then they are each nonzero polynomials of degree at most $k$, so by the induction hypothesis they each have at most $2^{n-1}-2^{n-1-k}$ zeroes. Zeroes of $p$ correspond to zeroes of $r$ if $X_n=0$ and zeroes of $q+r$ if $X_n=1$, so $p$ has at most $2^{n-1}-2^{n-1-k}+2^{n-1}-2^{n-1-k}=2^n-2^{n-k}$ zeroes.
This argument can be generalized to any finite field: if $p$ is a nonzero multilinear polynomial in $n$ variables of degree $\leq k$ over a field $F$ with $d$ elements, then $p$ has at most $d^n-(d-1)^kd^{n-k}$ zeroes (the number of zeroes of a degree $k$ monomial).
The proof is essentially the same except that in the induction step you must consider all the polynomials of the form $aq+r$ for $a\in F$, not just $r$ and $q+r$. If any of these polynomials is $0$, then at most one is $0$ (otherwise $p$ would be $0$), and they all have degree at most $k-1$. Adding up the zeroes of $p$ for each possible value of $X_n$ then gives that $p$ has at most $d^{n-1}+(d-1)(d^{n-1}-(d-1)^{k-1}d^{n-k})=d^n-(d-1)^{k}d^{n-k}$ zeroes. On the other hand, if none of the polynomials $aq+r$ are zero, then they all have degree at most $k$ and we find $p$ has at most $d(d^{n-1}-(d-1)^kd^{n-1-k})=d^n-(d-1)^kd^{n-k}$ zeroes.
Best Answer
Here are some more details. In fact we can prove the stronger statement that every function $\mathbb{F}_q^m \to \mathbb{F}_q$ is represented by a polynomial (which is even unique if we ask for the degree in each variable to be less than $q$). By linearity it suffices to show that a function which is zero everywhere except at a specific point is a polynomial, and by translating it suffices to show that a function which is zero everywhere except at the origin is a polynomial. This polynomial is easy to construct: it is just
$$(1 - x_1^{q-1})(1 - x_2^{q-1}) \dots (1 - x_m^{q-1}).$$
By Fermat's little theorem (or rather the mild generalization to finite fields, I don't know if it has a name) this polynomial vanishes unless $x_1 = x_2 = \dots = x_m = 0$, and at the origin it is equal to $1$.