Others have given RAW and RAI answers, based on rules of this item. I will instead turn to the instructions given to DM's in the Adventure's League DM manual, the closest thing (if there is such a thing) to "How a DM should adjudicate".
Always follow this golden rule when you DM for a group: Make decisions
and adjudications that enhance the fun of the adventure when possible.
I would posit that being paralyzed for a full minute is not fun for a player, nor is having an easily incapacitated enemy, that has no opportunity to fight back, fun for the party. Therefore, the subsequent saving throws should not automatically fail.
For myself, what makes a game fun is narrative coherence: Things working with a logic that makes sense and can be predicted with absolute and perfect knowledge (noting that few non-DM players have absolute or perfect knowledge, and those that do generally only have it over a limited time and area e.g. from scouting or divination spells).
The issue presented is that the paralyzed condition prevents a character from making STR or DEX saving throws (or more accurately, causes the character to fail them). Narratively, this is because STR and DEX saving throws require action, which paralysis prevents. DEX saves are dodging or turning to evade or minimize getting hit. STR saves are bracing to ward off blows knocking one down or back, and flexing to break bonds and restraints. Since one cannot take these actions when one is paralyzed, one fails.
So, narratively, what is being done by the saving throw? I would say that it is resisting and recovering from the force of the blow of Rod of Lordly Might. Normally, I would say that this should be a CON save, as it is an internal shrugging off of effect, rather than an external action. I suppose that the designers wanted spread out the saves, since the rod already has a CON save, and to give more weight to STR, already a lower classed defensive attribute. Therefore, the STR save should not auto-fail.