To be fair, state and local governments would have to increase the total tax burden on their populace to increase education funding, or makes cuts to other things in their domain. The federal government could certainly cut the military budget and grant those funds to state or local education programs, without increasing anyone's tax burden.
That said, my understanding is that the military budget mostly goes to salaries, so any drastic cuts would leave us with massive unemployment. You'd have to take things really slow to make that big a change in the labor force without pretty ugly side effects.
And don't forget, military needs teachers as much as anybody. When there's no war soldiers are on stand-by. What do they do? They train, which is really a form of education. They could learn many things besides how to use weapons. They could learn how to be teachers when they are ready to leave the military. :-)
That said, my understanding is that the military budget mostly goes to salaries, so any drastic cuts would leave us with massive unemployment. You'd have to take things really slow to make that big a change in the labor force without pretty ugly side effects.