So habs jetzt geschafft.
Ich hab jetzt einfach die Seiten auf denen cookies gesetzt werden alleine aufgerufen und nicht über die index.php included. Jetzt werden vorher keine Header mehr gesendet und die Cookies werden ordnungsgemäß gesetzt.
Danke nochmal an alle, die mir geholfen haben.
Von mir aus kann jetzt hier geschlossen werden.