mean average precision - pseudo code
Firstly for your question 2. The precision and recall is calculated across all images, for a single class. Not on a per-image basis and averaging across images. The "A" in "mAP" means averaging across different recall levels, as you stated in step 4.

For your question 1. Whether to report a same bounding box to both the cat and the dog class is a decision that your detection algorithm should make, not a decision that the evaluation function should make. You can imagine that input to the evaluation script to be a ranked list for each class, for example:

class [dog]                        |  class[cat]                        |  class[foo] ...
image=17, score=0.98, bbox=[...]   |  image=41, score=0.75, bbox=[...]  |  ... 
image=33, score=0.60, bbox=[...]*  |  image=07, score=0.45, bbox=[...]  |  ... 
image=93, score=0.55, bbox=[...]   |  image=33, score=0.40, bbox=[...]* |  ...
...                                |  ...                               |...


The evaluation script will calculate the AP for each class and it won't care whether the same bounding box (*) appears in different classes.

So for your detection algorithm, you can try different strategies and see which one achieves higher mAP.