Stored by emergency below, as it seems that documentation widely spread over the world can’t have a complete, working, config file for prestashop in nginx. Here’s one, that worked perfectly without any weird issues with 404-errors, etc.
Don’t forget to check your hostname and/or eventually SSL configuration for port 443.