OK.
After some time, I found a working solution.
My problem was, that I wrote the header-commands AFTER some output. According to the php documentation, this is forbidden.
So all I did is this, I created a new .php-file and checked if the session (in which I previously stored the needed information -  filename and download-command) was set correct. On the previous page, I received the POST-information, stored it into the session and redirected (also with header-command) to the newly created php-file.
Then I wrote these header-commands:
    header('Content-Type: application/octet-stream');
    header('Content-Disposition: attachment; filename="'.basename($filename).'"');
    readfile($filename);
And now, the download works from all browsers (also IE!).
Here is all my code, I hope this could help someone:
1st page (where I receive the POST-infos):
session_start();
...
...
if(isset($_POST["galerie_submitBt"])){
    if($_POST["galerie_submitBt"] === "Herunterladen") {            //Das Herunterladen muss in einer eigenen Datei passieren, bevor jeglichen Outputs
        $_SESSION["download_Screenshot"] = true;
        $_SESSION["filename"] = "/var/www/_old/pictures/".$_POST["filename"];
        header("Location:modules/php/download_Screenshot.php");
    }
}
?>
<!DOCTYPE html>
<html>
    <head>
       <title>...
2nd, new created php-page (where I actually download the image):
session_start();
if(isset($_SESSION["download_Screenshot"])){
  if(isset($_SESSION["filename"]) && file_exists($_SESSION["filename"])) {
    $filename = $_SESSION["filename"];          //Filename also includes the path! (absolute path)
    header('Content-Type: application/octet-stream');
    header('Content-Disposition: attachment; filename="'.basename($filename).'"');
    readfile($filename);
    unset($_SESSION["filename"]);
    unset($_SESSION["download_Screenshot"]);
  }
}