Alright, there is a lot to unpack here. I'm going to handle it one at a time.
I guess cEDH isn't about fun so much as it is about winning.
It's definitely still about having fun, but everyone's goal is to win the game. You don't see someone playing
Possibility Storm just because it's fun; they have it because it helps them win the game.
I always thought stax a way to slow the game down. I never saw a considerable advantage to running any of them because no one has fun when they're out.
You don't necessarily need stax that hurts everyone. You can instead look for pieces that will help in your playgroup. As an example,
Notion Thief is great in many situations, because almost everyone uses wheel effects or mass draw at some point.
Containment Priest stops creatures from being cheated into play (also stops that Vannifar we've been talking about).
Scavenging Ooze is excellent grave-hate. And
Magus of the Moon punishes people who spent money on their land-base. You don't necessarily need stax that harms everyone, you can instead tweak your stax effects to suit your playgroup.
While on the topic, is it worth it to waste a removal spell on a stax card if it isn't shutting you down, merely slowing you down? Assuming it isn't slowing you down enough to lose to the stax player. Most likely someone else will want to remove it.
You generally want to remove stax if it's stopping you from winning the game. If it's something that is hurting your opponents more than yourself, you should probably leave it. If the stax effect is slowing you down so that you can't play, then it is worth removing. What's more important is timing. You should always aim to remove stax on the End Step before it becomes your turn, that way you are the first to take advantage of the stax piece being
gone.
Krenko and Locust God aren't particularly competitive commanders.
I suggested these commanders because it is better to gradually make your decks better than is it to trial-by-fire your ass straight into competitive. It's what I did, and I know a lot of people get intimidated when they go into competitive. Not necessarily you Red_Wyrm, but the other people in your playgroup.
So start with high-powered decks first. I can vouch for Krenko, because it was my first deck.
The Locust God and
Krenko, Mob Boss are good because you can win with combat damage (what you're familiar with), but as the deck grows stronger, it will become more combo-centric (which is more cEDH style). Of course, as you get more into the competitive scene, you'll still be able to stand your own, but you won't be winning as often. This is kinda where my Krenko deck is at now; to strong for casual, not quite strong enough for competitive. If ever you want help upgrading those decks, let me know. I'd rather post my tips in the deck comments section than here.