Why won’t this rewrite rule work?

You have to make your rewrite rules account for the paged parameter, because otherwise they won’t. It would look somewhat like shown below.

function test_add_rewrite_rules() {
    add_rewrite_rule(
        'businesses/(eat|stay|play)/(.+)/page/([0-9]+)/?$',
        'index.php?post_type=businesses&display_category=$matches[1]&filters=$matches[2]&paged=$matches[3]',
        'top'
    );
    add_rewrite_rule(
        'businesses/(eat|stay|play)/page/([0-9]+)/?$',
        'index.php?post_type=businesses&display_category=$matches[1]&paged=$matches[2]',
        'top'
    );
}
add_action( 'init', 'test_add_rewrite_rules' );