Concerning the question of a reference for maximizing $k$:
A polynomial with all coefficients $\pm1$ is called a Littlewood polynomial, see, e.g., http://en.wikipedia.org/wiki/Littlewood_polynomial. The question of Littlewood polynomials vanishing to high order at $x=1$ is in the literature. See, e.g., Daniel Berend and Shahar Golan, Littlewood polynomials with high order zeros, Math Comp 75 (2006) 1541-1552, freely available at http://www.ams.org/journals/mcom/2006-75-255/S0025-5718-06-01848-5/S0025-5718-06-01848-5.pdf Executive summary; some numbers are known, some bounds are known, much remains to be done.