Definitely possible. You need 3 things:
1)A MapView. You need to sign up for a Google Maps id, they have some tutorials for implementing one where you do. The Maps API has functionality for showing your location and for putting pins on the map.
2)You'll need to get your own location for your calculation. This is a simple use of the LocationManager and Location classes.
3)You need to get a list of the stores with their latitude and longitude. At startup you parse the list, add them to the map overlay, and you can find the distance between you and them using the Location class's distance functions.