Would HSTS be effective if the Proxy's CA is in the trusted store?
The public key pinning built into Chrome and Firefox is ignored if the certificate is signed by a CA which was explicitly imported by the user (i.e. trusted but not built in). This is to support the common use case of legal SSL interception in security devices and software, i.e. to detect malware even in encrypted connections.
I'm not sure about the HSTS header, but I assume that the behavior would be the same.
Is there any way for me to protect against this MITM attack server side?
You can not detect which CA gets used on the client side. What you can do is to require a client certificate. Both legal and illegal MITM will not be able to transport the original client certificate through the MITM so they will either fail (in most cases) or they need to rewrite the client certificate too which you can detect on the server side.
Of course even with requesting a client certificate you will not be able to detect clients where some software (malware or not) gets access to the decrypted traffic by injecting into the browser directly, i.e. using browser extensions or DLL injection or similar techniques.
Like have the server check the client to ensure the right client is being used.
All you can do on the server is ask the client and check the answer. Since the client can lie to the server you could make it hard to lie by obfuscating the code and then asking for things which can be only answered by the client executing the code in the right way. But this can be the right client, the wrong client which understood the obfuscated code or the wrong client just instrumenting the original code.
What you really want is a remote attestation that you not only deal with an original unmodified client but that also no other process can somehow control the behavior of this client. To get this you have to start much deeper, i.e. usually you already need to have control of the clients hardware etc. I recommend that you look into the techniques they've tried to harden XBox and Playstation so that only original and unmodified games can be played and how often ways were found to evade the protection techniques. Or how Sony tried to control their customers PC to prohibit the ripping of their CD's by silently infecting the PC with a root kit.