Add new columns on existing or auxiliary table?
You haven't specified a database platform, but my experience with MS SQL server is that you should put those fields in the same table, unless you need them separate for other reasons (like if a single store can have multiple addresses).

Any performance concerns you have can likely be resolved with proper indexing, based on how you believe the table will be queried.