Windows 10 update ruined my GRUB menu

Have you tried running Boot-Repair?

It worked for me with a similar issue. This software repairs common issues with boot and grub menu entries. And if it can't solve a certain issue, it outputs a report which you may paste here so that the issue may be understood better.

You may install and run it on Ubuntu through the following commands:

sudo add-apt-repository ppa:yannubuntu/boot-repair    
sudo apt-get update
sudo apt-get install -y boot-repair && boot-repair

I hope it can work out the issues with kernel entries you described!

It might not hurt to run efibootmgr in a Linux terminal to clean out old boot entries. I had a similar issue and wrote a how to on a different forum...

How To Fix: No boot device found.

In my case, when the computer boots I can press the F2 key to get into a system "Setup Utility". Note that this is before any GRUB menu is shown. In the Setup Utility there is a section called "Boot" and there is a list of different boot options, coming from different operating systems that I have installed. In my case, there is one Ubuntu entry, two Fedora entries and one for Windows. (Fedora appears twice because I installed Fedora on two different occasions.) Here is what it looks like for me, the list I'm talking about is in the lower part, under "EFI":

(Note that on your computer it may look different, but with a bit of luck you will have something similar.)

This is great, because it lets me choose which one I want to use, by ordering them, the one on top will be used. In my case I have chosen Ubuntu, which means that I get the GRUB menu created by my Ubuntu installation.

So to fix your problem, try to find the corresponding settings on your computer (could be F2 or some other key you need to press when it boots) and reorder the list of EFI entries to put Ubuntu on top, then you should get the Ubuntu GRUB menu when you boot.