That took a bit more work than usual.
There was a few missing components and it I did not find a single source to know how to address the issue.
I had a hard time installing the virtualbox guest addition in Fedora 23. I kept getting errors about missing kernel headers, missing gcc and the fact that the x.org was experimental so it could not complete the installation.
The first few issues were easy to address:
sudo dnf install kernel-headers
The only catch was that my installation was with Kernel 4.2.3 but since the update channel had 4.2.8 headers available the latest got installed which did not match the kernel version I was running.
Lesson learned: update everything before installing new packages
The second component to add was the gcc:
sudo dnf install gcc
If you are up to date there is no issue to worry about otherwise you may get a mix of versions for the dependencies that will not work.
The last issue had the solution in the /var/log/vbox-install.log.
sudo make oldconfig
After that I ran the vbox guest addition installation and it completed without error. A restart and everything was working between the guest OS and the hosting one.