Using Arduino To Control Boot Sequence of PC
So it might depend on how you implement it. With an Arduino Uno, your options for creating an HID device are limited to either reprogramming the 16u2 (which will require an ISP) or using a software USB implementation (like V-USB). If you go with the first method I'm pretty sure that will work as it will be a native USB connection. As for the second method, I'm not sure how well V-USB responds to having the USB host turning on while it is running. The best thing to do is just try it and see how well it works.

The bigger challenge you will run into is being able to select your PC operating system. Because this will be a one way connection, there is no way of knowing what state the computer is in and whether or not it is time to press a key yet or not. This means you will have to be timing things fairly accurately, which can be tricky unless you are careful. The internal oscillator is not very accurate (but probably still accurate enough) and interrupts used for communicating with USB can block the main loop. That is not to mention any variations the computer might have in its boot process.

A good alternative method would be to set up a bootloader on your PC that can be controlled via a serial port. GRUB2 is a popular one that does support a serial console. All you would need to do is add a level adjuster to adapt the Arduino UART to RS232, then set up the code to wait for the GRUB prompt and then send the command necessary to select which OS you wish to use.