How does the time complexity of block cipher change with increase in key length? I am interested especially in the case when the keylength exceeds the length of the plaintext. 

Intuitively, it should be harder to crack the key with an increase in key length even if it exceeds the plaintext length but does it actually hold true or there any caveats to this particular scenario?
Usually we want a block cipher to be resistant to an exhaustive search attack on the key, if the key space $\mathcal K$ is the set of all binary strings of length $n$ then for a particular $k$ the attacker would have to search against $2^n$ possible keys, so the key length is chosen to make the mentioned attack infeasible.

Even if the cipher is proved to be computationally secure there is another (sometimes underestimated) security issue related to the cipher block size.

When we encrypt a message of arbitrary length it gets broken in chunks and the cipher is used within a particular mode of operation (ECB, CBC, etc) and because of the birthday paradox if the block size is not large enough the cipher could be vulnerable to a birthday attack which shows that after $2^{m/2}$ message blocks, where $m$ is the block size, we already have a 50% probability of having a ciphertext block collision and therefore leaking information about the original plaintext blocks.

For example 3DES works with key of length 168, which makes theoretically the exhaustive search attack unfeasible$^*$, but it's designed to accept blocks of 64 bits which means that after we collect $2^{32}$ encrypted blocks ($\sim$32GB of data) we expect to have a collision with 50% probability.

$^*$there is a known attack that runs in time $2^{112}$ instead of $2^{168}$