In Cruz Bay, there are 4 main markets. Listed in order of distance from the ferry dock you have Dolphin Market, right on Centerline Road at the new roundabout in the center of town. Then is Starfish Market & Starfish Gourmet Market on the first level of the Marketplace on South Shore Road. Then Pine Peace Mini Mart past the gas station, at the bottom of Jacobs Ladder, on South Shore Road. And finally, St. John Market, also on South Shore Road on the other side of Jacob's Ladder. (Jacob's Ladder is the steep hill you encounter on your way to the Westin).
In order of price, lowest to highest they are Pine Peace Mini Mart, Dolphin and St. John Market (managed by the same people, so the prices are pretty much the same) and then Starfish Market.

Pine Peace, cheapest, but not a lot of fresh produce and all meats are frozen, friendly service, but a cramped store. I prefer this market over all others and stop here first and get anything I can from them.

Dolphin/St. John Markets, good produce (most of the time), not much in the way of fresh meats, but otherwise pretty well stocked. St. John Market has friendly staff, and some of the staff at Dolphin is friendly, and some of them not.

Starfish Market has the only deli counter with both hot and cold items, the best selection of meats, good produce section, the best one stop shop, but the prices are considerably higher than any of the other markets. Also, they have there beer/wine/liquor in their sister store Starfish Gourmet. It is right across the hall, so not that big of a deal, but also not the most convenient thing to have. Starfish Market has the worst reputation for customer service, but their Gourmet Market has very friendly staff.