How do the ‘tag’ and ‘category’ (default) taxonomies do ‘save_post’ action?

It’s informative to check out the /wp-admin/post.php file, that contains the edit_post() function that calls wp_update_post(), which is a wp_insert_post() wrapper.

Here’s a skeleton for saving the assigned category terms:

/**
 * Saving assigned category terms (skeleton)
 */
add_action( 'admin_action_editpost', function()
{
    add_filter( 'wp_insert_post_data',  function( $data, $parr )
    {
        add_action( 'save_post_post', function( $post_ID, $post ) use ( $parr )
        {
            if( 
                    isset( $parr['_wpnonce'] )
                &&  wp_verify_nonce( $parr['_wpnonce'], 'update-post_' . absint( $post_ID ) )
                &&  current_user_can( 'manage_categories' )
                && function_exists( 'wpse_save_assigned_cats' )
                && ! did_action( 'wpse_save_assigned_cats' )
            ) {
                wpse_save_assigned_cats( $post_ID, $parr );
                do_action( 'wpse_save_assigned_cats' );
            }
        }, 10, 2 );
        return $data;
    }, 10, 2 );
} );

where our helper function wpse_save_assigned_cats() is based on the edit_post() function:

/**
 * Helper function based on the cat/tax handling of the edit_post() functions
 */
function wpse_save_assigned_cats( $post_ID, $parr )
{
    if( ! empty( $parr['tax_input']['category'] ) && $post_ID > 0 )
    {       
        // Change the comma seperated string of category names,
        // in $parr['tax_input']['category'], to an array of cats id
        $input_cats = explode( ',',  trim( $parr['tax_input']['category'], " \n\t\r\0\x0B," ) );
        $clean_cats = array();
        foreach ( $input_cats as $cat_name )
        {
            // Don't allow empty categories
            if ( empty( $cat_name ) )
                continue;

            // Check if there already exists such a category
            $_cat = get_terms( 'category', array(
                'name'          => $cat_name,
                'fields'        => 'ids',
                'hide_empty'    => false,
            ) );                

            // The category name already exists
            if ( ! empty( $_cat ) )
            {
                // Collect the (first) category id
                $clean_cats[] = intval( $_cat[0] );
            } 
            else 
            {
                // Create the category, since it doesn't exists
                $cat_id = wp_create_category( $cat_name );

                // Collect the category id
                if( $cat_id > 0 )
                    $clean_cats[] = $cat_id;
            }
        }
        // Current post's category IDs
        $cats = (array) wp_get_post_categories( $post_ID, array( 'fields' => 'ids' ) );

        // Unique array of category IDs
        $post_categories = array_unique( array_merge( $cats, $clean_cats ) );           

        // Assign the categories to the current post    
        wp_set_post_categories( $post_ID, $post_categories );
    }   
}

Previous Answer:

Here’s my Friday answer, so it might need some testing 😉

I just re-registered the category taxonomy as non-hierarchical with:

        'hierarchical' => false,

Then the category box showed up like this:

and saving terms worked as expected.

Here’s my testing code snippet, so you can try it further:

add_action( 'init', function()
{
    global $wp_rewrite;
    register_taxonomy( 'category', 'post', array(
        'hierarchical' => false,
        'query_var' => 'category_name',
        'rewrite' =>  array(
            'hierarchical' => true,
            'slug'         => get_option('category_base') ? get_option('category_base') : 'category',
            'with_front'   => ! get_option('category_base') || $wp_rewrite->using_index_permalinks(),
            'ep_mask'      => EP_CATEGORIES,
        ),
        'public' => true,
        'show_ui' => true,
        'show_admin_column' => true,
        '_builtin' => true,
        'labels' => array(
            'name'                          => __( 'Categories' ),
            'singular_name'                 => __( 'Category' ),
            'search_items'                  => __( 'Search Categories' ),
            'popular_items'                 => null,
            'all_items'                     => __( 'All Categories' ),
            'edit_item'                     => __( 'Edit Category' ),
            'update_item'                   => __( 'Update Category' ),
            'add_new_item'                  => __( 'Add New Category' ),
            'new_item_name'                 => __( 'New Category Name' ),
            'separate_items_with_commas'    => null,
            'add_or_remove_items'           => null,
            'choose_from_most_used'         => null,
        ),
        'capabilities' => array(
            'manage_terms' => 'manage_categories',
            'edit_terms'   => 'manage_categories',
            'delete_terms' => 'manage_categories',
            'assign_terms' => 'edit_posts',
        ),
    ) );
} );