Flush Rewrite Rules on init or rest_api_init?

Flushing rewrite rule should not be done on routine basis, as stated per codex:

Don’t do it on any hook that will triggered on a routine basis.

You should either do it via the plugin activation hooks, or the theme switch hooks:

add_action( 'after_switch_theme', 'wpse315001_flush_rewrite_rules' );

register_deactivation_hook( __FILE__, 'wpse315001_flush_rewrite_rules' );
register_activation_hook( __FILE__, 'wpse315001_flush_rewrite_rules' );
function wpse315001_flush_rewrite_rules() {
    flush_rewrite_rules();
}

Either of the above, and it should be done AFTER you have registered your custom post types.

Also, you should flush the rewrite rules after your plugin is deactivated. This makes sure no invalid rule is left.

However, like every other problem, this has a nasty workaround too. If your rewrite rules contain a semi-unique keyword, you can get the rewrite rules from the options, run a search on it and flush the rules only if necessary:

add_action( 'init', 'wpse315001_flush_rewrite_rules', 99999 );
function wpse315001_flush_rewrite_rules(){

    // Get the rewrite rules
    $rules = get_option('rewrite_rules');

    // Check if your semi-unique rule exists in this string
    if ( ! strpos( $rules, 'your-rewrite-rules' ) ) {
        // Flush'em All!
        flush_rewrite_rules();
    }
}

Maybe not the best solution, but it’ll do.