If the attacker has 1 billion 4KB (random-noise) messages and sha256-HMACs for those messages (all using the same key), can they calculate the key that was used, before the universe dies?
Not, that should be not possible, at least if you have a good key.
All this is only valid as long as SHA-256 is still a secure hash algorithm and not broken. To be precise, as long as HMAC-SHA-256 is not broken.
Does the attacker have any informations about the messages (other than the length and that they are "random-noise")? If he/she doesn't: No, there's no way an attacker could get the key in real life conditions. They would have to brute force HMAC-SHA-256, and that's not possible if you use normal computers with non-ignorable probability. Every message has far higher entropy than anything possible to brute force.
If the enemy knows all messages: Well, it's all about your key. In the past, there was a need to have a key for hashes, but the common structures of hashes were not suitable to just put the key before the message. HMAC was invented to solve this problem. It has some nice security proofs which basically say "It should not be possible to get the key as long as the hash function is still secure and the key good enough." - the RFC 2104 has more explanations and some links for further informations.
Well, is your key good enough? If your key is anything under 64 bit long and at least one message known by the attacker, than you have lost. Brute forcing 64 bit is not easy, but doable. If your key is longer than 64 bit (something like 80 bit or better 128 bit or higher) then you have to think about entropy. If your key is fully random and an attacker doesn't know any pattern about it, than is the entropy as high as the length in bit, but if your password is something like "password1234", than it's pretty easy to brute force, despite having 96 bit (for 8 bit per character). Good passwords are alone a pretty complex topic, so I won't include them in this answer. If you need to know more about secure passwords, use the search engine you like the most for something like "good password" or "choosing secure password".