So after tinkering around for a while I finally found a solution. I used boot-repair, thanks to hermancain for the suggestions
But not for what, it is indented for (since that didn't work), but to get into my linux filesystem and get my grub-config (
/boot/grub/grub.cfg) and searched for the entry for my Linux-boot. I made a picture with my smartphone and then I booted to
boot-repair again, which has GRUB and instead of booting boot repair, I pressed C for the console.
Now I repeated the steps from my
set root=(hd3,gpt5) ## it was hd1,gpt5 in my config-file, but with ls, I found the right partition in this environment
linux /boot/vmlinuz-linux root=/dev/sdb5 rw quiet ##my config-File used the UUID, but I didn't want to type that in
initrd /boot/intel-ucode.img /boot/initramfs-linux.img
After finally booting into my Linux, I opened a console and executed
Now, I could finally select the right boot-entry in my BIOS again(The P5 entry disappeared and I have still no idea, what that was supposed to be).
I think, I should go with the times and will install systemd-boot like suggested by cylgalad in the next few days, so something like that won't happen again.
I have some other problems with my PC, so I did reset BIOS. Than I had the same problem. I even already had
systemd-boot installed. So, this didn't change anything. The problem is obviously that when BIOS scans the HDDs for the first time, it only recognizes the Windows Boot Manager, but not the Linux Boot Manager in the EFI partition. I guess reinstalling GRUB,
systemd-boot notifies BIOS about that and that is when you can select it in the boot menu. The P5 entry was also there, the second time and disappeared after reinstalling
The motherboard with this problem is an ASUS M5A99X EVO R2.0 with the latest BIOS version (2501) installed.