Hi Harsha,
Since you have replication in place, you only need to upgrade the policy store from one policy server per environment. Replication will take care of the rest.
To answer your secondary question, it would do no harm if you repeated this procedure from each policy server since it's static data and thus would not change even if overwritten in this way, but this would be a needless step.
Regards,
Pete