If you didn't restrict $V$ to be of the form $\exp ( i\alpha (k))$, the (normalized) $V$ that would maximize $V^{\dagger } AV$ is the eigenvector $V_{max} $ corresponding to the largest eigenvalue of $A$.
So, often, a first good approximation would be to maximize the overlap between $\exp ( i\alpha (k))$ and $V_{max} $, i.e., maximize $\sum_{k} \exp ( -i\alpha (k)) V_{max} (k)$. In many cases, this will already be exact, e.g., if the spectrum consists of one maximal eigenvalue and all smaller eigenvalues degenerate. This maximum overlap is achieved by choosing the phases $\alpha (k)$ such that all the terms in the sum over $k$ add up constructively, i.e., $\alpha (k) = \arg (V_{max} (k))$.
Then you could check, by varying the $\alpha (k)$, whether you're already maximizing $V^{\dagger } AV$. If not, at least you have a decent starting point in many cases.
Although, in general, the answer will depend on the details of the spectrum and the eigenvectors, one more thought about the generic large-$n$ case, where by "generic" I vaguely mean a well-behaved spectrum and eigenvectors with entries of magnitude $1/\sqrt{n} \, $: Let's also normalize your trial vectors to unity by giving the elements a normalization factor $1/\sqrt{n} $. Then, the best overlap achieved with the eigenvector of maximal eigenvalue is of order $1$, whereas the overlap with other eigenvectors is typically of order $1/n$. Then, typically, if you rotate away from the best overlap vector by a finite angle, you reduce the contribution from the largest eigenvalue by a finite amount, whereas you typically won't have a concomitant coherent reduction of strength in the low part of the spectrum that might offset the effect of weakening of the contribution of the largest eigenvalue - of the order of $n$ eigenspaces would have to conspire to produce an effect in a common direction. So, there's a chance the maximum overlap vector above works pretty well in a typical large-$n$ case.
