Customer Targeting for CRM Marketing Campaign
Can you share all available columns in the data set? its hard to tell what data is there to use.
Given the data you show, I would have started with some explaratory analysis:
Group data per shops, check user activity ( how much purchases they do per month/week, what is AOV, LTV, etc).
Idealy, its good to use email marketing, because its cheaper that paid ads and you have list of users that can be mailed - given the low costs of email marketing campaigns, you can basicaly target all users that stopped shopping in given places and allowed you to send them mails.

Additional approach: you can use paid ads for remarketing and geo-based ads to recover lost clients - given the fact that you want to cut the costs, its might be beneficial to retain only loyal customers ( which have more that 2 or 3 transactions, this number should be based on your average sales per client). 

So, answering the questions:


What are your recommendations for the campaign? Should we do it? How should we target and why?
Should we do it?


Select all users that were lost after opening new shop and calculate lost income per month (or week, based on your data) - you want to know how much money you can expect from recovered users, this can be your marketing spend baseline ( Recoverd Income - Costs - Margin ~ Marketing Budget). Marketing Budget + Recoverd Income will indicate if its logical to run the campaign.

What are your recommendations for the campaign?

I would start with email - cheap and effective, we can use targeting in emails based on what items users buy, their gender and age.  If you have segment of loyal users with high income - you can develop dedicated email campaign based on their needs, give bigger discounts ( its good to know why they left in the first place).


Is there any additional customer information that would help you? What is it? How would it help?


Any data that will help to better segment users will be usefull - age, gender, social status, all this info can influence email campaigs.
Also it would be good to have data about costs and effectivness of Paid Remarketing Campaigns - based of this data we can try to use remarketing for our loyal customers.


Have both stores been impacted similarly? How has customer shopping behavior been affected?


Split data per shops, calculate statistics, do some good-looking and easy to undestand graphs, cant say more without actual data.

Hope this help!

EDIT

Thanks for sharing data, here is my opinion about this task:

You can split data before-after 25 of may, and target users that have losses in sales comparing to period before 25 of may. 

Based on Customer_Data dataset, it looks like you have user that can be mailed and emailed, so you can launch 2 campaigns for different users based on Mailable_flag / Emailable_flag flags.

Talking about losses: Based on given data is looks like your shops lost around 3k in sales and ~60 transcations for both shops after 25 of may and the losses are equal amont users that can and connot be emailed.

This leads us to a point of "additional" data - ideally you want to know the past performance of mailed and emailed campaigns to adjust the targeting.

Also the thing I havent done - you should calculate LTV ( basicaly how much money the users brings you per month) - if some users have very low LTV, you dont want to spend money advertasing them. 

I`ve attached ipython notebook with brief workflow for you to check . Please, be aware that its just my ideas and they cant be totally wrong :)