Should millis() be stored in a variable once each loop, or called for every reference?
The primary downside to calling a function each time is that it may take more CPU cycles to complete the overall loop. The difference in CPU cycles, if any, depends on the actual implementation of the function and how the compiler optimises the call. For low-CPU sketches, this difference is probably unnoticeable.

Generally speaking, it is good programming practice to avoid calling a function more times than is necessary. Really the function should be called directly only if you have reasons to believe, based on desired timing and procedure order, that using the same return value in multiple places could create problems. In the example sketch given, there would be almost no functional difference between using a variable or calling the function inline.

Another advantage to using a variable is that you can give it a name that makes the code clearer to understand. In the example given, the relationship between currentMillis and previousMillis is very clear. In the case where a function returns a more complex object, such as a class or structure instance, using a variable (of the appropriate type) can be really useful since this would allow multiple members of the returned data to be accessed without calling the function multiple times. In fact, even in the given example, the function would have to be called twice since currentMillis appears twice in the loop.

As far as memory goes, an unsigned long uses very little.