Is there a name for this phenomenon in cognitive science?
What you are describing is a number of things that in general have to do with attention and memory.
The first one of them is priming. Memory can be both conscious and unconscious, or declarative and implicit, and attended vs unattended. I've always found the names a bit confusing, but in short there is a lot of information that your brain stores without you being in the know. The priming bit comes from experiments where sets of words were presented to test subjects as part of a context, that is they were not part of the main activity or focus, and later when tested for another set of words that included those same first words, the subjects scored higher on recognizing them. An advertising billboard on the highway or street is designed to take advantage of priming.
The second thing at play here is what's called pop-out search ( Treisman & Gelade ,1980). When a target of a visual search can be identified by a single feature such as color, it pops-out, in the image below, how long does it take you to find the special K ?
So, back to the candy bar example: by staring longingly into the first vending machine, you primed yourself with candy bars unknowingly, and upon encountering a second one, your undirected visual search immediately noticed the one that was different from the first set.
Perhaps it had some early evolutionary advantage?
I believe it could, imagine you live in the savanah so something like this might be your day to day, you are familiar with it, yet if a lion or other predator were to be in the mix, this popout search + familiarity would help you spot it.