I guess for this you need hierarchical BU structure for this, so make stuture like this.
All Group (Root Level BU)
Region (child of All Group BU)
Store (child of Region BU)
And assign relevant users to their respecitve divison and make security role such way they opportinuty/contact previlage is set as Parent Child Business unit.
Regarding contact opening you can programiticaly share relevant contact with Store BU and that way.
Please refer following article for more information on this
https://msdn.microsoft.com/en-us/library/gg309524.aspx?f=255&MSPPError=-2147217396
MayankP
My Blog
Follow Me on Twitter