Is your store in the USA?
That can make a difference. In USA, we are always thinking of the name being found easily on google or in a normal printed telephone book.
It also makes a difference if it is in America, aimed at one ethnic group. For example, an Indian store near me, is called 'Indo-American Foods', they sell mostly food, a few kitchen implements used for that style of cooking, etc. 'Apna Bazaar' is a good name for another store that sells more variety of items - it sells Indian food, Hindu worship items, clothing, kitchen tools and rents videos in Indian languages.
If it is in USA, I would avoid the word 'Shop' in the name, as it sounds repetitive to Americans. Unless it says something important about the business, like 'Asia Baru Shop and Save', for a discount store.
If you sell a variety of things, often in the USA, the word 'Variety' or if an ethnic store, Bazaar. Such as 'Indo-American Variety'.
To Americans, 'Mart' usually means a very small store, very small floor space. If your store is very small, 'Mart' is good.
'Market' often is used for a store that sells food as it would be bought from a farmer - not packaged foods, but fresh vegetables, fruits and fresh meats. In a 'Market' the food is in bins, and people choose their own and put them in a plastic bag for weighing. But you do see 'Market' used sometimes for other types of stores.
'Asia' in a name (In the USA, anyway), should be for a store that sells Asian products - products brought here from Asia - specialty foods, spices, ethnic clothing, books, videos, etc.
So I like the name 'Asia Baru Market' for a store in USA, IF you have specialty products (imported from Asia).