Maybe someone will find it usefull so I'll write how i solved the problem. At least it looks solved for now.
The issue seems to be in the Windows regional settings.
If you used English (United States) as language settings (usually it should only be if regional settings are set to US, but it seems that windows display language and other language settings as well could cause the problem somehow). So, If you have this settings, the paper size will be set to Letter (vice versa for people that have problem wiht A4 and want Letter -> they need to switch from A4 region to Letter region).
In order to "clean" the language settings, I changed Windows display language to English (UK), removed US from the preferred languages and also changed Administrativre language settings (system locale and copy to welcome screen and new user accounts). The regional setting were ok even before, but if you have US, change it to A4 region (as for example UK if you want English).
Make sure that your printers are set to A4 (or whatever you are looking for). You can do it by going to Printers & Scanners and change manually each printer. Consider that in most printers you have to change paper size in multiple places. In Printer properties (both tabs: Device settings and Advance/Printing Defaults) and Printing preferences. You can also do it through Windows Powershell (Win + X and run Terminal (Admin)). I first run the following code:
Get-Printer | ForEach-Object {
$printerName = $_.Name
$printConfig = Get-PrintConfiguration -PrinterName $printerName
[PSCustomObject]@{
PrinterName = $printerName
PaperSize = $printConfig.PaperSize
}
}
After that you can use (depending on what paper size you want for which printer):
Set-PrintConfiguration -PrinterName "Xerox" -PaperSize A4
After that, restart the computer.
When you log in again, remove the printer and restart computer again.
After restart, install printer again (Add device).
It should be ok and the paper size for that printer should be A4 in Adobe.