You may tried all methods to make your Linux VM in Virtual Box full screen but nothing worked.Right?
I also encountered the same issue, so here is the solution that worked for me.
I was using Kali Linux and by default the guest additions comes preinstalled but that didn't solve my problem. I was not getting the window full screen.
The below screenshot is before solving the issue. I tried to install the guest additions manually and noticed that the OS was unable to find the kernel headers.
Try the following steps to fix.
1) Update the modules and packages.
sudo apt update -y && apt upgrade -y && apt dist-upgrade
2) Install the headers.
sudo apt install linux-headers-$(uname -r)
3) Now install the guest additions tool.