How does a TLB lookup compare all keys simultaneously?
Computer hardware is fundamentally parallel.  Even a modern single CPU core is pipelined, meaning that at the same instant in time, one physical part of the CPU is initiating a fetch of an instruction, another is decoding a slightly earlier fetched instruction, another is calculating the new result of a slightly earlier decoded instruction, and another is writing back the results of a slightly earlier calculating instruction.

One of the reasons a layer 1 cache in a CPU is so small, and so much more expensive per bit of storage, is that the tag cache portion of the address is broadcast to multiple cache lines, and each of them has some independent hardware logic to compare this tag value against its own tag value in parallel, each independently calculating "that tag matches what I have" or "it doesn't match me".