You simply need to visit the Settings > Permalink page (you don’t have to do anything there) after saving the settings.
If I had written the saving function myself, I could just call flush_rewrite_rules()
Not quite. flush_rewrite_rules() would have to be called after the custom post type is ‘updated’ to reflect the changes, that is, after you register it. So you would need to call it on the next page load, after the CPT is registered.
You could use a transient to trigger flush_rewrite_rules() on the next (and only the next) init (and after CPT is registered). To be clear, flush_rewrite_rules() is expensive and shouldn’t be called regularly, this is why I suggest simply telling your plug-in users to visit the Settings > Permalink page after altering any permalink options – that way the rules get flushed only when its really needed.