Oh... Now I know where the problem is... it's not that it can't play any video, it's that all my videos are on another hard disk! I can't keep all my videos on my SSD so, my Video folder is a symlink to a folder on my traditional hard disk. So I guess I'll have to grant totem the ability to read on my hard disk.
However, for the other errors, I'm using Debian testing updated, I tried on X.org and GNOME + Wayland and the results are the same. I do have gnome-nightly applications installed via flatpak, because Debian is slow at packaging GNOME 3.24. I added this line to /etc/apparmor.d/local/usr.bin.totem: > owner @{HOME}/.cache/mesa/** rwk, because otherwise it errors on many other files in that folder. That fixed the mesa cache problem. Then I added this line to /etc/apparmor.d/local/usr.bin.totem: > /var/lib/flatpak/exports/share/icons/** r, and that solved all errors. I can now open videos on my home with a clean audit.log. Thanks.