Browsing through menu related stuff in the DOM lead me to nothing, but Google turned up this blog entry by Harbs: http://in-tools.com/article/scripts-blog/showing-text-formatting-overrides/
-- and then I could find it in the DOM, well hidden:
So it seems you have to set the state of a menu action. The action in itself can be attached to one or more menus (MenuAction, where checked is read-only, is a parent class of ScriptMenuAction, and there it is read/write), probably to ensure that if a certain menu item appears in more than a single menu, they are all "updated" at the same time.
Harbs' example always sets 'checked = false' and changes the menu text to indicate its current state, but I assume one can also toggle the checked state.
Thank you! (and thanks Harbs). That did it. Didn't dig deep enough, dagnabbit.
The best place for changing action properties such as checked, enabled and name is an event listener for BEFORE_DISPLAY.
There you can also peek at the selection, consider the active document and so forth.