 Solution

For perfect balance, $k=2^{n-1}$ and the all-zero probability is zero. For other balances the one-shot outcomes overlap the constant case. Repeat Deutsch-Jozsa algorithm and declare nonconstant upon any nonzero result. Constants are never misclassified; a $k$-balanced function fails after $R$ trials with probability $q^R$, $q=(1-2k/2^n{)}^2$. It suffices that $R\ge \log ϵ/\log q$, using that many oracle calls.