There are two issues here (just like in your question). I'm going to explore both of them. First, the Conceptual Problem and then the Practical Implementation.
Here's the deal, something that everyone should just know, but I've found is really hard for people to accept.
We cannot protect a computer from itself.
What I mean is that when trying to keep something secret on a computer, especially on the HDD, but really, also in memory, that thing will not really be secret. We can build very complex OSes and data silos, however, in the end, there's a Trusted Computing Base (TCB) and then there's everything else.
In this case, you've got a secret (Message Authentication Code Key or MAC key) or as the other post/commenters have suggested you'll have to use an asymmetric Pub/Priv Key. That key material is just information and you've got to put it somewhere and that location has to be accessible to programs running on the computer without human intervention. That means either it will be in the clear or it will be encrypted with some other Key (password from a human or yet another crypto key). You don't want human intervention, which means that the password or the second crypto key needs to be stored.
Now, we are in a recursive problem and there's no base case! Why? Because we cannot make a computer keep a secret from itself. At least, not if it has to use that secret, and your program needs to do just that. So, in the end, your key material or that encrypted key plus the second key used to encrypt it will be available to at least one process on the computer, and therefore, be copyable (as information) to any other device on the planet. Security blown.
Really, you might as well keep the key in the clear (unencrypted), in an O/S protected file, harden your servers to attack and monitor the network and servers for problems. Of course, people freak out when you suggest keep it in the clear b/c "OMG, you didn't ENCRYPT it?!" Ok, fine, so protect it with encryption, but don't lie to yourself about how safe it truly is. Laws to keep credit card data protected save Marketing Face, they don't really protect anything. The most important part of the laws are customer notification upon break in and theft of personal data. That is important.
In the end, someone could find a way to steal your MAC Key and whatever else you use to identify the remote server, and therefore, spoof the identity of the remote server. The best you can do is to use the crypto algorithms as they've been designed and for the purposes they were intended and then protect and monitor.
Bruce Schneier discusses this. (1) Proper algorithm selection and implementation. (2) Proper System configuration. (3) Active Monitoring.
Also, as an aside I recall reading a research paper that showed how to pick keys off a hard disk by scanning and looking for highly entropic regions of short (key) length. The idea is that most stored computer data is of regular form. Sections of data that don't have patterns (appear random) are most likely encrypted data or keys. Encrypted data will tend to be grouped. Keys will tend to be isolated. INOW, stored key data on a hard disk actually jumps out at you if you're looking for it in the right way.
Good luck with that.
Your improper use of a crypto algorithm has lowered your security resulting in an attack more likely than the theft of your machine key from your machine.
You're using MAC Keys as a means of identification. Please note that Eve the Eavesdropper could discover your MAC key by watching one exchange and then off line attacking the message+MAC to reveal the key. This could be an expensive attack; however, depending upon the system and the data, it could be worth the cost.
In this case, you've abused one crypto algorithm (Message Authentication) for another purpose - server identification and trust. Instead, you need to separate Authentication of the server from Authentication of the message (which is really misnamed and causes confusion, so I call it Integrity protection, which is what it is).
Any good Authentication algorithm (4 step handshake authenticating both client and server) creates session keys which can be used for Privacy (session encryption) and Integrity (message authentication). Note, I write keys because you shouldn't use the same key for both. The best algorithm you can use provide Perfect Forward Secrecy, which these days means DH at 2048 bits. However, DH is subject to MITM attacks, so you need a way to mitigate that. I would suggest using SPEKE or DHEKE, whichever one is no longer under patent protection. You could also do what TLS does and sign the DH ephemeral with an RSA key, but now you're into PKI.
At this point, I'd say that you could just use TLS+RSA and make sure it's properly configured and limit your root certificates or use two-way authentication in which you don't need Root Certs and each peer validates the other. This will provide exactly the type of security you'd like to have.
So, if you're going to roll your own authentication system, really dig into the philosophy of good crypto system design and do it right. You'll probably wind up replicating Kerberos or TLS, but you'll learn a lot. Here's what happens when you think you understand enough about this and still build it incorrectly.
Or, don't roll your own and just adopt Kerberos or TLS and take advantage of everything they have to offer.
I suspect you know which way I think you should go.