The answer was to set VerticalAligment="Center" of ViewBox element
<Grid Background="{StaticResource ApplicationPageBackgroundThemeBrush}">
<Viewbox VerticalAligment="Center" Stretch="UniformToFill" StretchDirection="Both">
<MediaElement x:Name="Player" HorizontalAlignment="Stretch" Margin="0" VerticalAlignment="Stretch" Source="myvideo.mp4"/>
</Viewbox>