We solved the problem. Here our findings:
The placement files were fine.
The "Map" Module had a migrations.cs-file with this line:
ContentDefinitionManager.AlterPartDefinition(typeof(MapPart).Name, builder => builder.Attachable());
typeof(MapPart).Name results in "MapPart", not "Map", even though the ContentPart is displayed as "Map" in the dashboard. In the code you have to use the string "MapPart".
So the only thing we needed to change was
public int UpdateFrom6()
builder => builder