O Ctrl-S funciona bem no Excel 2016, bem como em todas as versões anteriores do Excel.
Inicie o Excel em Modo de Segurança para garantir que não haja nenhum complemento atrapalhando suas teclas de atalho.
O Ctrl-S agora salva a pasta de trabalho?
Nesse caso, você tem algum software instalado que substitui o atalho de teclado Ctrl-S. Remova esse software e o Excel responderá corretamente ao Ctrl-S novamente.
Editar: Para encontrar o suplemento incorreto, remova todos os suplementos. Então veja se o Ctrl-S funciona. Traga de volta um add-in de cada vez e teste após cada ativação.