It's not a "who goes first" issue. All Bonuses/Abilities activate at the exact moment they can, unless they are canceled.
In this case, Saddy's Ability and Sheitane's Nightmare
bonus would both activate. Now because Saddy's ability says that Shetaine's Bonus is canceled, that free's Saddy's bonus.
Basically to my understanding here's what happens.
Saddy's Ability and Shetaine's Bonus both activate.
Shetaine's bonus cancels Saddy's bonus.
Saddy's Ability cancels Shetaine's Bonus
Since Shetaine's Bonus was canceled it no longer applies and Saddy's Bonus now works.
Attack Calculations begin and Saddy
gets her +2 Power
Now this may not be exactly per the way it's coded, but the bottom line is, if something is canceled then it will fail to work. Even if it's effect is to cancel something else. (See below for the only exception to this rule)
When Two of the same cancellation type run head to head (ie a Bonus that Cancels Abilities, and a Ability that cancels Bonuses (or vice versa), or 2 Abilities that cancel Abiltiies or 2 Bonuses that cancel Bonuses) they basically cancel each other out.