How to prevent Public Key from being replaced entirely? I am using RSA to sign my license file using Microsoft CNG API. I am signing the license file and sending the file with the public key to the end user.

Now I have a problem, what if someone's signs the license file content with entirely new set of private\public key pair. Then they can easily replace my public key with their own key and the license file with the one signed by new corresponding private key. Is their some guideline I am missing? Also Can it be prevented If I store the Public key in a certificate store?
Also Can it be prevented If I store the Public key in a certificate store?


Well, an adversary could probably just overwrite that entry and mount the same attack as before.


  Now I have a problem, what if someone's signs the license file content with entirely new set of private\public key pair.


What you have stumbled across is the "trust problem" of public key infrastructures (PKIs). Namely that you need a binding between a public key and an entity.

In this case you want a binding between your public key and your identity as the software vendor. The simplest solution would be "pin" the public key (eg the SHA256 hash of it) in the verifying program so that it only accepts the public key / signature pair if the hash matches.  Of course this could be patched out of the software by an adversary wanting to elide the license check, but so could be the check altogether (DRM is hard)...


  It would be really get if you could add a few more lines on "pin" the
  public key part.


The idea of pinning is the same as is used for trusted root CAs in browser. You keep a copy of the public key you trust in your software package. Then when verifying the signature, you check whether the received public key matches (any of) the stored, "pinned" public key. If it does you proceed with verification otherwise you immediately return with an invalid signature error. If binary size is a concern you can also hash the incoming public key and compare the hash against a hard-coded hash.

In theory you could also pin a public key of your own "CA" and force all signatures to present a certificate signed by that CA, but it seems like the simple pinning of the data-signing public key should suffice and the additional scalability in number of keys is not needed.