mmmpp1111

AAA_cat部分に/page/2/用のリライトルールを追加することで自己解決しました。

functions.php

          register_taxonomy(
            'AAA_cat',
            'AAA',
            array(
              'label' => 'AAAカテゴリ',
              'singular_label' => 'AAAカテゴリ',
              'labels' => array(
              'all_items' => 'AAAカテゴリ一覧',
              'add_new_item' => 'AAAカテゴリを追加'
              ),
              'public' => true,
              'show_ui' => true,
              'show_in_nav_menus' => true,
              'rewrite' => true,
              'rewrite' => array('slug' => 'AAA'), 
              'hierarchical' => true
              )
            );
            add_rewrite_rule('AAA/([^/]+)/page/([0-9]+)/?$', 'index.php?AAA_cat=$matches[1]&paged=$matches[2]', 'top'); //追加部分

上記を追加しても最初は４０４は解消せず、
Custom Post Type Permalinksを一旦停止し、再度有効化（再起動）したところ、
無事 /AAA/BBB/page/2/　が表示されました。
同じところで悩んでる方が解消できれば幸いです。