Edited to add part III
$\newcommand\ket[1]{\left| #1 \right>}
\newcommand\ketbra[1]{\ket{#1}\left< #1 \right|}$
If you have $N=2^n$ possible polarization at angle $k\frac\pi N$ with $k\in[ 0 .. N-1 ]$, the possible states of $\nu$ photons can be written
$\ket{k,\nu}=\left(\frac{\ket0+e^{2ik\pi/N}\ket1}{\sqrt2}\right)^{\otimes\nu}$.
A key parameter for the probability of confusing two different angle $k$ and $k'$ is the scalar product
$$\left<k',\nu\middle|k,\nu\right>=\left(\cos\left([k-k']\frac\pi N\right)\right)^\nu$$
I. Discrimination between two states
If I restrict the problem to the discrimination between two angles $k$ and $k+1$, the optimal theoretical measurement is well known and is given by the Helstrom discrimination. The success probability is given by
$$P_c=\frac12\left[1+\sqrt{1-\left|\left<k',\nu\middle|k,\nu\right>\right|^2}\right]$$
If you want $P_c\ge 1-\varepsilon$ with $\varepsilon\ll1$, this becomes
$$\begin{align}
\left(\cos\frac\pi N\right)^\nu&\le2\sqrt{\varepsilon(1-\varepsilon)}\\
\nu&\ge\frac{\frac12\log\varepsilon+\log2+\frac12\log(1-\varepsilon)}{\log\left(\cos\frac\pi N\right)}
\end{align}$$
If $N=2^n\gg1$, we have $\cos\frac{\pi}{N}\simeq 1-\frac12\left(\frac\pi N\right)^2$ and therefore $\log\left(\cos\frac\pi N\right)\simeq-\frac{\log e}{2}\left(\frac\pi N\right)^2$
We have then
$$
\nu\ge N^2\frac2{\pi^2}(-\ln\varepsilon-\ln2-\ln(1-\varepsilon))
$$
So in this case, the number of needed photons in of the order of $N^2=2^{2n}$, with a prefactor depending on $\varepsilon$.
The Helstrom measurement itself seems difficult to perform, but an adaptative set-up (the Dolinar receiver) compining interferometric displacement and single photon detectors allows to achieve this performance when the states are coherent states. I suppose a similar set-up can be built for polarizations.
II. The more general problem, estimated through entropy
Your problem is not a discrimination problem, but the distinction among many angles. The amount of information one can encode in $\nu$ photons identically
polarized along an arbitrary angle $\theta$ is given by by the von Neuman entropy of the mixed state $\rho_\nu=\int d\theta\ketbra{\theta,\nu}$.
Rewriting $\ket{k,\nu}$ and some algebra can show that this entropy is the entropy of the binomial distribution of parameters $p=\frac12$ and $n=\nu$.
This entropy is $\frac12\log\frac{\pi e\nu}{2} + O\left(\frac1\nu\right)$. An order or magnitude of the $\nu$ needed to distinguish between $2^{2n}$ polarization is then given by
$$\begin{align}
n\simeq\frac12\log_2\frac{\pi e\nu}{2}\\
\nu\simeq\frac{2^{2n+1}}{e\pi},
\end{align}$$
Which is of the same order of magnitude than the discrimination.
III. Unambiguous discrimination
Another way to look at the problem is the number of photon needed to perform a na unambiguous discrimination (UD) measurement. A UD measurement is a measurement which never makes an error, but sometimes fails. Of course, given the non-orthogonality of the states, this failure probability can never be zero, and is 100% when the number of photon is too small. The problem is a special case of the one Chefles and Barnett studied here here. The first non-zero success probability is for $\nu=N-1$, but this probability is small ($\nu2^{-\nu}$). It increases every time $\nu$ increases by 2, but I've found no simple expression (and I've tried some time for a paper). I guess (from the previous parts) the probability becomes non-negligible only when $\nu\sim N^2$.