Three suggestions:
1. Create Your Own Metabox
This is your original idea: when creating/editing the Store post type, the metabox will display a dropdown with all the available Managers of this post type.
For that, use Bainternet’s answer to this Question as a starting point, and change the get_categories for a get_posts of your CPT.
This will be stored as post meta and retrieved normally with a get_post_meta.
2. Use Post 2 Posts Plugin
wordpress.org/extend/plugins/posts-to-posts/
I never really used this one, but I know it’s done for this kind of scenario and its author is a WordPress heavy weight…
In both plugin cases, read the documentation for the retrieval method.
3. Use Advanced Custom Fields Plugin
wordpress.org/extend/plugins/advanced-custom-fields/
Another actively maintained plugin with plenty of custom fields goodies.
The field types Relationship or Post Object can be used for this purpose.
Bellow the screenshots of a test configuration using the post types Movies and Actors with a Relationship field (more complex than Post Object, which would produce a simple dropdown).
Field Configuration
click to enlarge
Field Result
click to enlarge
