Hi - Alma Delicatessen is near the bus station. If you take the number 27 bus from Coventry Train station and get off at the bus station, then walk past the Transport museum it's on your left past the Tudor Rose pub. They also had a selection of Polish stuff.
Plenty of Polish shops all around Cov. There's a stall in Coventry Market I know, plus the one on Ball Hill Pebbles mentioned (again, taking the 27 bus towards walsgrave Hospital and getting off by Stoke Library - it's opposite the library and says Polish delicatessan). There's also one on Far Gosford Street and one on Clay lane (if you've been to the one by Stoke Library cross the street and walk down a ways, turn left at the traffic lights by Barclays Bank and that's Clay Lane, the Polish shop is almost all the way down on the right).
Re:getting lost in Cov - if you go to the bus station and walk past the Sainsbury's up the hill, just after the Flying Standard is a tourism office which should have maps.
