Hi, spaniard butting in!

Charcutería is a place where you buy cheese and meats that are ready to eat (cured or boiled ham/turkey; chorizo and other sausages…). As opposed to a carnicería, where fresh meat is sold.

The etymology of ultramarinos sounds about right (haven’t checked), but yeah it’s just an old term for grocery store.