If G is PRNG, there are two issues:
First, not all PNRGs are cryptographically secure. You have to use a cryptographicaly secure PRNG, a CSPRNG. If the PRNG was not cryptographically secure, one might, for example, perform a known-plaintext attack.
Second, if $n = |k|$, we have only $2^n$ possible keys. For a given cryptotext, there are only $2^n$ possible plaintexts. Theoretically, this provides some information: it changes the probabilities. Some possible plaintexts $m$ of the length are impossible (i.e. there is no key $k$ such that $d_k(c) = m$). The other plaintexts are thus more probable.
Assuming there is not a pair of keys $k_1, k_2$ such that $k_1 <> k_2 \wedge d_{k_1}(m) = d_{k_2}(m)$, then $Pr[M = m] = 2^{-|m|}$, but $Pr[M = m| C = c] = 2^{-min(|k|, |m|)}$. For $|k| < |m|$, i.e. when the key is shorter than the plaintext, these probabilities will differ.
More practically speaking, attacker often knows format of the data or the data maybe contain a hash.
Of course, if $n$ is large enough, then exhaustive search is virtually impossible. In fact, this scheme is used: It is called a stream cipher. (The definition of a stream cipher might be slightly different, but it is virtually the same.)