If you did not create recovery media before your Ubuntu install it looks as if you will need a new copy of Win 8 as that will be the only CoA sticker on your new machine. You can use that key to download an ISO file from here click here If you look at the options you can select to burn the ISO file to either DVD or USB Flash Drive. In your case you will need the Flash Drive option. Hope this is of some help. By the way Win 8 isn't quite as bad as it seems to be made out. With a read of the posts in the Win 8 Forum you will see that there are ways to make it behave similarly to Win 7 and still be much faster to boot.
Surface Pro (2017) vs Surface Pro 4