Check in BIOS secure boot section if there is an option for "Allow Microsoft 3rd Party UEFI CA" or similar.
On newer devices (at least from Lenovo) you can't secure boot anything except Windows by default.
By enabling this option you can secure boot the Microsoft signed Linux bootloader shim.
Thanks for the tip.
This option is not available in my case.