Wordpress pagination 404 error "/page/2" - what to do?

The problem mainly arises because permalinks set to Custom Structure /%category%/%postname%/. I understand WordPress assumes "page" is a post from the category.

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.

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, '/', true ), '/' );
                }
            }
        }

        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;
}

For more details , you can check on the url https://wordpress.stackexchange.com/questions/172958/custom-permalink-structure-leads-to-be-404-on-pagination