For the record, I just encountered this with the latest version of Veeam Endpoint Backup on 2 different Windows 2008 R2 servers.
The setup installer seems to be checking 2 registry keys/values. If either are present, it throws this error (waiting for a restart), even if you have already restarted.
For some reason, on some servers, either key/value is supposed to be deleted on reboot, but sometimes they don't. I don't know why.
The registry keys are:
HKLM\System\CurrentControlSet\Control\Session Manager\PendingFileRenameOperations <- this last entry is a DWORD inside the Session Manager key
HKLM\Software\Microsoft\Windows\CurrentVersion\WindowsUpdate\Auto Update\RebootRequired <- this last entry is a key, with 1 or more DWORDs inside of it.
If you have rebooted and are still getting this error, it should be safe to delete the above registry values (delete just the DWORD for the 1st, and the whole key in the case of the 2nd, not just the DWORDs inside of it) - (standard disclaimer: as with any registry edit, do this at your own risk, I am not responsible for any damage, etc). I did this on 2 servers and was then able to run the installer as normal.