Are \choose and \align incompatible?

Do not use {n \choose k} in LaTeX (it is a plain TeX command). The recommended way in LaTeX is \usepackage{amsmath} in the preamble and then \binom{n}{k}. (You have then also \tbinom and \dbinom for text and display styles also.)

Simple answer: Don't use \choose, or don't use amsmath, or live with the warnings.

There is a long explanation of why this kind of construct is deprecated in the document technote.pdf which is part of the amsmath docs, in the section "4 Why do \over, \atop, \above [. . . withdelims] give a warning when I add the amsmath package?"