Custom permalink structure leads to be 404 on pagination

That is totally normal behaviour. If you want to remove category base you will need to write some custom rewrite rules, not simple rules I must say. From my point of view, removing category base requires a extra job in each request that is worthless because it doesn’t provide any advantage for SEO or for better site navigation. Some popular plugins, like WordPres SEO by Yoast, had this option in the past and removed it some time ago. But this is just an opinion.

Configure category base to . (dot), put this code in the functions.php of your theme, or better in a plugin, and flush the rewrite rules (code from this post in Daily Web Kit):

add_filter( 'category_rewrite_rules', 'vipx_filter_category_rewrite_rules' );
function vipx_filter_category_rewrite_rules( $rules ) {
    $categories = get_categories( array( 'hide_empty' => false ) );

    if ( is_array( $categories ) && ! empty( $categories ) ) {
        $slugs = array();
        foreach ( $categories as $category ) {
            if ( is_object( $category ) && ! is_wp_error( $category ) ) {
                if ( 0 == $category->category_parent ) {
                    $slugs[] = $category->slug;
                } else {
                    $slugs[] = trim( get_category_parents( $category->term_id, false, "https://wordpress.stackexchange.com/", true ), "https://wordpress.stackexchange.com/" );
                }
            }
        }

        if ( ! empty( $slugs ) ) {
            $rules = array();

            foreach ( $slugs as $slug ) {
                $rules[ '(' . $slug . ')/feed/(feed|rdf|rss|rss2|atom)?/?$' ] = 'index.php?category_name=$matches[1]&feed=$matches[2]';
                $rules[ '(' . $slug . ')/(feed|rdf|rss|rss2|atom)/?$' ] = 'index.php?category_name=$matches[1]&feed=$matches[2]';
                $rules[ '(' . $slug . ')(/page/(\d)+/?)?$' ] = 'index.php?category_name=$matches[1]&paged=$matches[3]';
            }
        }
    }
    return $rules;
}