An efficient way to compare two large data sets in SQL

Using EXCEPT is in my opinion the way to go here, but you might want to reconsider the use of the temporary table. By doing so you are effectively duplicating your data in memory, which will slow you down. If the indexes you need exist on the source tables (as I suspect), just compare the appropriate SELECTS:

SELECT StoreKey,ProductKey FROM table WHERE sales BETWEEN date1 AND date2
EXCEPT
SELECT StoreKey,ProductKey FROM table WHERE sales BETWEEN date3 AND date4