Block template suggestions
The Drupal theming system has a concept called "template suggestions". When a theme hook is invoked, Drupal checks if the theme hook is implemented as a template or as a function. In case of a template, All preprocess functions for that theme hook are invoked. This means that every module or template can add its own data to the variables that will be made available to the template. Those variables are passed around as a large array, $variables. This array can contain a list of template suggestions as a nested array called $variables['template_files']. Drupal will later reverse that list and use the first existing template it can find. See the documentation on drupal.org for more details.

Now what you can do is:


Add a function to your theme's template.php named [themename]_preprocess_[themehook] (eg. function mytheme_preprocess_block(&amp;$variables) {} )
In that function, construct the desired template name suggestions
Add those suggestions to the $variables['template_files'] array


By the way, if I'm not mistaken you cannot use the region name in the template suggestion, because at the time the block is rendered, it is not yet known in which region the output will be shown.

PS 1: It helps if you tell us which Drupal version you're using.

PS 2: I'm voting for this question to be moved to https://drupal.stackexchange.com/