variable api vs custom table
Not an answer per say; more of a critique of some of your assumptions with variables. 


  If I'll use the variable api then on each block view I need to load
  the variables separately i.e. 5 variables load( ~5 database fetch
  queries)(if block no results is enabled) and 1 variable load(~1
  query)(if block no results is disabled for that block)


In actuality all variables get loaded on EVERY pageload with a single query, including cache_page hits (think anonymous users) unless your doing something special ($conf['page_cache_without_database'] = TRUE;, varnish, or boost). variable_initialize() get's called very early; dig though drupal_bootstrap() a little bit to see. So a variable get doesn't cost you a db query, but it's not a good idea to abuse the variables db table because the more data that's in there (KB), the slower Drupal gets.

Actual answer:
My personal preference is to use cache_get_multiple() if your looking at 100s of items to get; unfortunately it looks like _block_render_blocks() makes this hard to do; the function that calls hook_block_view_alter(). So in this case a cache_get would be the easiest way to go. Another option is a cache loader; all in one cid (harder to manage writes) or get all cid's for the enabled blocks block_page_build() or $blocks = drupal_static('block_list'); with drupal_static(). What's ideal depends on many factors, biggest one being how large (KB) is the cached data; if its small a loader &amp; drupal_static() might be the fastest option. If you have a large amount of data then doing individual cache_get() call might be better due to the lower memory usage and not loading unused data. See https://www.lullabot.com/blog/article/beginners-guide-caching-data-drupal-7 for more details on caching.

Also be aware of cores built in block caching. Use it if at all possible. See https://www.drupal.org/project/blockcache_alter for ideas and usage.