We seem to have different settings because my Window Maker application menu is updated automatically every time I install/remove apps. I cannot say why it doesn't work for you because I've never had any problems with my menu. I've got the "menu" and "menu-xdg" packages installed, if that makes any difference. You can do "dpkg -l | grep menu" to see if you've got these too.
It is possible to modify some aspects of the right-click menu in Window Maker while still keeping the auto-update feature. At least you can decide where individual programs should appear in the menu by copying the appropriate menu files from /usr/lib/menu/ to /etc/menu/ and editing them there. If you install non-debian apps, you can make menu entries for them in /etc/menu/. However, the changes in /etc/menu/ require running "update-menus" and restarting Window Maker before they show in menu.
You can use the same method to associate keyboard shortcuts to certain menu entries. For example, I've got a file /etc/menu/aterm that reads:
I can open aterm by pressing the Shift and F1 keys at the same time. It's also possible to move aterm to another menu directory by editing the section entry.
Window Maker appears to be the only window manager where the files in /etc/menu/ actually have any effect on menus, so you're lucky in asking specifically about Window Maker menus.