UE4.8:
Confirmed that adding a DefaultGameUserSettings.ini file to the Config folder (ala 's response) will allow you to start deployed exes in fullscreen.
I used the following (make sure there are no whitespaces at the beginning of each line if copying):
[/Script/Engine.GameUserSettings]
bUseVSync=True
WindowPosX=-1
WindowPosY=-1
bUseDesktopResolutionForFullscreen=True
FullscreenMode=0
LastConfirmedFullscreenMode=0
Version=5
I removed the ResolutionSize and LastUserConfirmedResolutionSize lines because they were causing a default resolution different from my monitor, stretching the image. Also, FullscreenMode needs to be 0.
DefaultGameUserSettings.ini is copied automatically when deploying, so fullscreen works correctly by default when running the executable that is generated in Saved\StagedBuilds