How do I correctly delete a project completely including media files?
The Editing Guide says that you can simply delete the project when starting MC. Does this also delete the media files?
In MC 2018.x you first had to delete the media files with the Media Tool.

The process for deleting a project has not changed in 2020.4.

they mean that you can delete an Avid Project in the project selection window.

project selection window is the first window you get on startup, delete key removes highlighted projects.

Simply put, deleting a project does not delete media.

If you would like help sorting this out, feel free to connect with me https://calendly.com/kenton-van-natten/help

Also worth noting you don't need the project to exists to delete avid media created in that project.

Open any project and in Media tool you can select the Project and drives. 

The project list is extracted from the Project metadata embedded in every media file Avid makes.

AMA linked media can't be deleted this way as its outside Media Composer.