See below for the solution that worked for me, on OSX 10.9 (Mavericks).
This issue seems to have been in and out of forums for the last 5 years or so. The most commonly suggested solution is to edit the VirtualBox Info.plist file and add LSUIPresentationMode = 4. Documentation can be found on the apple developer website, under: information property (plist) key reference -> launch services keys.
This should work for most apps, but because of how VirtualBox operates, it only provides a temporary fix. Switching apps, exiting full-screen or changing spaces causes the menu to re-appear. My solution is to force VirtualBoxVM.app (NOT VirtualBox.app), to run as an agent app; by editing it's Info.plist file. This has the effect of disabling the menu bar (in windowed AND fullscreen mode) and also, unfortunately, removing the virtual machine from the application switcher. On Mavericks, the dock will still appear in fullscreen after moving the cursor to the bottom of the screen, and then moving it down again. It is actually quite difficult to get it to appear, so this seems to be an adequate solution. After starting the virtual machine, or exiting fullscreen, the menu bar may reappear. But it is non-functional, and will disappear after switching apps, etc. This is a hack that achieves the goal of disabling the VirtualBox menu bar in fullscreen, but it also causes some weird behaviour and is not the best solution; but it may be of use to you.
Editing plist files can damage your apps or operating system; so keep backups of the original plist files, and don't change anything unless you understand what you are doing. You have been warned! This method also uses a text editor to modify the plist files, which can cause file corruption if there are any non-unicode characters present in the plist files (a distinct possibility). I have not had any issues yet, but you can use a different method if you are worried (i.e. a plist editor app, or defaults.write in terminal). Some plist files are encoded in binary, and further steps will be necessary if you are trying to edit them.
Go to Applications Folder
Right click on VirtualBox.app > Show Package Contents. Go to Contents/Resources; right click on VirtualBoxVM.app > Show Package Contents.
You won't have write permissions for the Info.plist file, so an easy option is to copy it the desktop; make the required additions; then move it back and overwrite the original file (admin password required). Copy this file (not the VirtualBox.app one!): Applications/VirtualBox.app/Contents/Resources/VirtualBoxVM.app/Contents/Info.plist
Add this line to the copied Info.plist file using a good text editor (I use gedit): " <key>LSUIElement</key> <string>1</string>", without the quotation marks. The command needs to be inserted at the correct place, i.e. between "LSCanProvideIMVideoDataSource" and "NSHighResolutionCapable"; or else it will not work.
Make sure VirtualBox is not running and move the Info.plist file back to the original location; overwriting the one inside VirtualBoxVM.app/Contents (admin password required).
OS X Mavericks actually keeps plist data in RAM, so logging out, restarting, or resetting the parameter RAM may be also be required before the Info.plist file changes will take effect. Then launch VirtualBox.app, and start up your virtual machine. The VirtualBox.app menu should still be there, but the VirtualBoxVM.app instance will lose its menu bar and application switcher icon.