Let's start with the preliminaries. The basic scheme has encryption defined as follows:
$$\mathcal{E}^{G, H}(x) = f(x \oplus G(r) || r \oplus H(x \oplus G(r)))$$
Some definitions:
- $f: \{0,1\}^k \rightarrow\{0, 1\}^k$ is a trapdoor permutation where $k$ is the security parameter
- $x$ is the message to encrypt
- $n = |x|$ is the bit length of the message
- $k_0 = k - n$ (the value of interest in out case)
- $G: \{0,1\}^{k_0} \rightarrow\{0, 1\}^n$ is a "generator" from $k_0$ bits to $n$ bits
- $H: \{0,1\}^n \rightarrow\{0, 1\}^{k_0}$ is a "hash function" from $n$ bits to $k_0$ bits
- $r \gets \{0, 1\}^{k_0}$ is a randomly selected $k_0$ bit string
The general idea behind setting $2^{k_0}$ to be much larger than the adversaries run time is to prevent the adversary from having a non-negligible chance of brute forcing the value of $r$. Recall that $r$ is a random $k_0$ bit string so there are $2^{k_0}$ possible values of $r$.
Suppose that $k_0$ was selected to be only a couple bits, in this case $\mathcal{E}^{G, H}$ is not secure under a chosen plaintext attack (IND-CPA). For an intuition of how to prove IND-CPA see this graphic. Briefly, if an adversary submits messages $m_0, m_1$ to be encrypted by $\mathcal{E}^{G,H}$ and gets back $c$ it needs to determine if $c$ is the encryption of $m_0$ or $m_1$. Here's how it does that:
$G$, $H$, and $f$ are all public , so the only unknown in the equation is $r$, which was randomly sampled. If $r$ is small enough (i.e. if $k_0$ is small) then an adversary can compute $\mathcal{E}^{G, H}(m_0)$ and $\mathcal{E}^{G, H}(m_1)$ for all possible values of $r$. Once it computes a value that matches $c$ the adversary knows that $c$ is the encryption of whichever message was input into $\mathcal{E}^{G, H}$, which means it has a non-negligible advantage in the IND-CPA game (i.e. the scheme is not IND-CPA).
So naturally we want to pick a $k_0$ that is large enough such that an adversary is unable to brute force the value of $r$. This implies the definition that $k_0$ be chosen such that the adversary's running time is significantly smaller than $2^{k_0}$ steps.
So to conclude, for values $k_0$ that are very small the results are catastrophic as you lose semantic security. For values $k_0$ that are very large there's no security drawback, but your permutation $f$ needs to be bigger which generally translates to a slower scheme (think RSA2048 vs RSA4096 for example).