Given a sha-512 hash of a value picked at random from the $2^{128}$ key space, how hard would it be to recover the original value? More specifically is it reasonable to assume that someone with the resources of a state actor can feasibly compute a rainbow table of all the sha-512 hashes of values within the $2^{128}$ key space?

Am I correct in assuming that the most efficient attack in this case would be to compute a rainbow table, given that sha-512 doesn't have any known vulnerabilities?
The answer, as SEJPM pointed out, is "no, a work effort one the order of $2^{128}$ SHA-512 computations would be infeasible, even by a three letter agency".

However, the other question was "would constructing a rainbow table be the most efficient attack?"  The answer is "it depends".

If the attacker was interested in just one SHA-512 hash, and had no expectation of ever needing to attack another hash (or, at least, one with the same salt; for example, known bits that are also included along with the 128 unknown ones), then constructing a rainbow table is wasted effort.  The takes a constant factor more work than simple brute force (just trying all possible 128 bit values, and hashing them), and has a probability of failure (if none of the chains happens to hit the target value, the rainbow table lookup will fail).

On the other hand, if the attacker expected to have a series of SHA-512 hashes, all of the 128 bit keys (and all the other parts of the hash the same known values), then constructing a rainbow table makes a lot of sense; yes, constructing it takes a long time (infeasibly long in this case), however once you've done it, looking things up in it doesn't take that long at all.