Are blocks still cached when "Cache block" setting disabled but "Cache pages for anonymous users" is enabled? I have a site which contains a custom block.  The custom block contains a menu based on a sub-set of the site's main menu.  The problem is that main menu is very large (~1300 items), so generating this particular menu in the block, is quite costly. According to hook_block_info() the block is configured to use DRUPAL_CACHE_PER_PAGE | DRUPAL_CACHE_PER_ROLE caching methods.

If I go to the site's performance configuration page I notice that the "Cache block" option is disabled; However, the "Cache pages for anonymous users" option is enabled.  

In such a situation would the block be cached or not? If it is cached, then would that only be for anonymous users?
TL;DR yes

Well, not per se. But page it appears on is cached, including that block. There is no separate item for the block in any cache in situation you described, but it won't be recreated anyway. Code for it won't be executed. And yes, in default Drupal configuration page caches works only for anonymous users.