Continuing this work, I have found the hard way that I was jumping out of the frying pan and into the fire when trying to use those Actions! Used within the script, the action-selected selection would be extremely unreliable and would disappear most of the time.
Then, I discovered this difference between graphic styles on paths and graphic styles on groups. It appears that Select same Graphic Style will select paths with a certain style, but never the groups. To select groups which have a graphic style applied, the item Select same Appearance works. Therefore, if I used "Find Style menu item" to get the same style art, the only time the parent group would be part of the selection is when all of the items inside have the style. This makes it much better: now I get an art object array from the selection using a recursive function and just use style.applyTo on the items which are not groups. Next step would be to select and replace the same style on all the groups. Using "Find Appearance menu item", it selects the groups which will have the graphic style applied to it which I want to replace, and as such all of the group's members are selected too. What if a member of such a group was also a group with the style on it? The document selection in this case goes to the topmost hierarchy, producing an array of non-nested groups which have the style on them. Since my goal is replacing a style, I can use a while loop checking for document selection being at null or 0 length and using Appearance menu item command to check for styled groups. As the styles get replaced, the menu item command will find nested styled groups, if any, all the way down.
This is how I now achieve graphic style replacement in a document: first get a selection of the Style menu item and apply the new style to all items; second, get a selection of Appearance menu item and keep replacing the style of selection's top-level groups and re-selecting via Appearance menu item until there is no selection.
I take back almost everything I said about app.executeMenuCommand, may it please have mercy on my transgressions.