Assuming that you are right that $k=2$ for $n=1$ (I have not verified this), it seems to me that $k=2$ for all $n>1$ as well.
One argument goes as follows. Suppose $p^{-1}(a) = q^{-1}(a)$ and $p^{-1}(b) = q^{-1}(b)$, where $a$ and $b$ are distinct complex numbers. Fix a point $x\in p^{-1}(a)$. For each point $y\in p^{-1}(b)$, let $L_y$ be the unique complex line through $x$ and $y$. Then the restrictions $p|L_y$ and $q|L_y$ are one-variable polynomials $L_y\to \mathbb{C}$ whose fibers over $a$ and $b$ are the same. Thus by the one-variable argument, you know $p|L_y = q|L_y$. In particular, $p$ and $q$ agree on $\bigcup_{y\in p^{-1}(b)} L_y$, which has non-empty interior. By analytic continuation, $p = q$.
[Edit: This argument is needlessly complicated. The fact of the matter is that on any complex line $L$ through $\mathbb{C}^n$ the restrictions $p|L$ and $q|L$ are polynomials $L\to \mathbb{C}$ with the same fibers over $a$ and $b$. Thus $p$ and $q$ agree on any complex line, and hence on all of $\mathbb{C}^n$.]