When you have E-8s who are not in compliance with the regulations, is it OK to correct them on their appearance?

Short answer: Yes.
TC 7-21.13 states the following regarding on the spot corrections:
"On-the-spot corrections are not only issued from the leader to the subordinate, but also include
tactful corrections from subordinates to leaders and corrections between peers. It is your responsibility to understand and adhere to the standard."
Understanding and executing are two different things however. Tactful is the key word in this situation. Unless the person you are attempting to correct is flagrantly violating the standard, the direct approach works better if you start with the assumption that the person you are correcting knows better and has overlooked something (like boot laces hanging out, headgear crooked, etc.) In that situation, most leaders will be grateful for the correction. Sometimes you can take the situation to another Senior NCO (your PSG for example) and allow them to make the correction. Senior leaders will take corrections much better from their peers than from privates. Another technique is to frame the correction in the form of a question. Example: PV2 Miller comes to MSG Jones and asks what regulation governs (insert deficiency here) because PV2 Miller isn't certain what right looks like based on leaders demonstrating different standards. Just make sure that you choose your battles wisely. If the MSGs that you refer to aren't being corrected by their supervisors or peers, whatever on-the-spot corrections that you make most likely won't stick. If that's the case, don't pursue it further (unless you really like pushups).
Edit: Additionally, make absolutely certain that you are in the right. Some regulations are not as black and white as they may seem at first glance. Others fall within the commander's discretion of a particular unit/installation. Make sure that you aren't attempting to enforce your opinion or personal interpretation of the regulation.

Yeah, that is a good idea. Feel free to do so.

Hell yes, correct them. Here's some real honesty, tact doesn't always work. In fact, 90% of the time, any NCO rank will embarrass you regardless of how you approach them. Be a big boy, tell them whatever they're doing is against regs. Truth is, they're going to rip you a new one and probably embarrass you, so at least be sure you're completely following regs before you try to correct. As an old SGM told me during an ass chewing, "you should correct me when I'm not right, but be a man and prepare to get ripped up. At the end of the day, I will respect your courage".

#1-Know your shit
#2-Don't throw stones if you live in a glass house (if you're chunky, don't rag on overweight people, etc)
#3-Be able to take an ass chewing EVEN IF YOU'RE RIGHT! Some people have egos that cannot handle constructive criticism. If you get an ass chewing, let it roll off your back. I've taken a thousand of them and have endured a phenomenal career, driven largely by my own ambitions. It's completely worth it for the funny stories you will tell in the future about some shitty leader you were smarter than. Use it as a learning experience as well. Every time you recognize a flaw, you are learning what NOT to do.

If they are a walking talking piece of chewed bubblegum, then for starters ENSURE that you yourself are squared away beyond contention, then approach these MSGs and respectfully and tactfully let them know what deficiency they are showing. I also recommend that you DO NOT do this in front of others. Ask to speak to them off to the side. As my units Detachment Sergeant, if I am a walking stick of wrong, then I would want my Soldiers to let me know.

It all depends whats going on. If its a range safety issue worry about consequences later and make the correction immediately with as much force as necessary. Ive seen E4s put hands on SFCs and MSGs on a range before and the NCOIC and OIC chewed them out when they started going after the SPC. If its about grooming or uniform wear Id advise caution, you really are taking your life in your hands haha.

A good leader is able to give and recieve correction, like the others have mentioned, make sure your 100% correct, do it in private, and respectfully. I always encouraged my people to correct non compliance regardless of rank.

I want to know why a PV2 is claiming SPC as his rank on RallyPoint?!

We take care of each other that's the bottom line and also remember we as enlisted set the example to our officers.

My advice is to do it anonymously through a discrete note