Background is not a Color but instead a Brush which is why it can't be animated directly with a ColorAnimation. Instead try the following.
<ColorAnimation
Storyboard.TargetName="btnRemoveBorder"
Storyboard.TargetProperty="(Border.Background).(SolidColorBrush.Color)"
To="#FFDEBA29"
Duration="0" />
With regard to the VisualStateManager question, one state from each state group can be active. So in the case of a Button for example, it can be in both the Focused and Pressed state. For this reason, you should try to design your states and control templates in such a way that does not depend on which state becomes active first. Usually this means you shouldn't animate the same element/property in two different state groups. But technically speaking, there's nothing preventing you from doing so. Whichever state the control goes to last (using the VisualStateManager.GoToState method) will take precedence.