I understand that if a block cipher has $k$-bit keys and $n$-bit input/output blocks, then if $k>n$, we can expect one message-ciphertext pair to narrow us down (I think?) to $2^{k−n}$ possible keys, right?
That is approximately correct (if the block cipher with the wrong key acts like a random permutation; this is generally a safe assumption); if block "one message-ciphertext pair", you mean "a single $n$-bit plaintext/ciphertext block.
However, that's not necessarily what we mean by a "message-ciphertext pair". We often want to encrypt messages that are larger than $n$ bits; to do this, we use a mode of operation (which uses the block cipher to encrypt larger messages); if we have a larger message (and we know the plaintext and the ciphertext of this larger message), then we usually (depending on the exact mode used) have a number of $n$-bit plaintext/ciphertext blocks.
The upshot of this is that if we have a $k$-bit message (and corresponding ciphertext), this is usually sufficient to allow us to recognize the key (with a possible 1 or 2 false hits; those can be eliminated if we take a message slightly larger than $k$ bits); if $k>n$, then we would get several plaintext/ciphertext pairs against the underlying block cipher