No. it doesn't have to be there. "Kokken har ændret menuen" is also perfectly acceptable. The only difference is very subtle: "Ændret på" is used when it's not a huge change; maybe the cook substituted one of the meals on the menu with something else. Without the "på" it would sound like she/he did a complete change of all the things on the menu.