You should add the -dFIXEDMEDIA switch:
gs \
-o output.pdf \
-sDEVICE=pdfwrite \
-sPAPERSIZE=a4 \
-dFIXEDMEDIA \
-dPDFFitPage \
-dCompatibilityLevel=1.4 \
input.pdf
-dFIXEDMEDIA is always required if you need to force a specific paper/page/media size and ignore the paper/page/media size specified in the document. Because PDF always has a paper/page/media size defined (PostScript might have, or might not have…).
(My -o ... is shorter and saves one from adding -dBATCH -dNOPAUSE — but works only for more recent versions of Ghostscript.)