Changing XAML style dynamically in Code Behind so that controls applying that style also reflect the change

You need to use DynamicResource so that it can be changed at run-time. You also need to replace the style with a new one, not try to modify the existing one. This works:

<StackPanel>
    <Rectangle Style="{DynamicResource key1}" Height="200" Width="200" x:Name="rect1"/>
    <Button Click="Button_Click" Content="Click"/>
</StackPanel>

Style style = new Style {TargetType = typeof(Rectangle)};
style.Setters.Add(new Setter(Shape.FillProperty, Brushes.Red));
style.Setters.Add(new Setter(UIElement.VisibilityProperty, Visibility.Collapsed));

Application.Current.Resources["key1"] = style;

It is also worth mentioning that styles are sealed once used and hence can not be changed. This is the reason why styles should be replaced by another instance rather than updated.