Found the solution for my issue:
Apparently you have to add the triggers within the ControlTemplate under ControlTemplate.Trigger. Andd after you've done that the thing with borders is that you have to set a TargetName in the Border tag and then set the reference (-> TargetName="XXXXX") to the properties which you've named in the border tag.
So:
<Window.Resources>
<Style x:Key="MenuButton" TargetType="Button">
<Setter Property="Background" Value="Transparent"/>
<Setter Property="Height" Value="40" />
<Setter Property="Width" Value="Auto" />
<Setter Property="Foreground" Value="White" />
<Setter Property="Margin" Value="45,0,0,0" />
<Setter Property="Template">
<Setter.Value>
<ControlTemplate TargetType="{x:Type Button}">
<Grid>
<Border Name="MenuBorder" SnapsToDevicePixels="True" BorderBrush="Black" Background="{TemplateBinding Background}" BorderThickness="0,0,0,2" >
<ContentPresenter HorizontalAlignment="Center" VerticalAlignment="Center"/>
</Border>
</Grid>
<ControlTemplate.Triggers>
<Trigger Property="Button.IsFocused" Value="True">
<Setter Property="Background" Value="Transparent"/>
<Setter TargetName="MenuBorder" Property="BorderBrush" Value="#FFED6A2B" />
</Trigger>
</ControlTemplate.Triggers>
</ControlTemplate>
</Setter.Value>
</Setter>
</Style>