Disclaimer: getting anything wrong with flashing might brick your device - this is not a manual. I am not responsible for any damage to your phone or data...
So I finally checked the software update availability on my Samsung Galaxy S5, and guess what - the Android 5.0 update was available. Finally. I cleared up some space on my phone (it claims that it needs 3 GB of free space for the installation) and started the update. It is a big image (1.4 GB), so it takes a while to download, then the phone shuts down, restarts, and starts to install. I started wondering when the installation process started at 25%, went down to 1, up to 20, 30% and then - "error". Phone restarts, everything OK except for the fact that I still have KitKat on my phone.
Tried again. Same result. Tried again. Same result. Googled it. No results. Nobody seemed to run into that same error. There was indeed an error message after the phone restarted successfully - "Try it again, try Kies or go to a service center" (I paraphrased). Service center? Nope, no time, plus I got the phone in Germany and I wont be in Germany for quite some time.
So I tried Kies. Downloaded the software, started the firmware upgrade - download interrupted at some point. Tried again. Tried again. Tried again - it started the installation process on the phone, finally. But it stopped at about 80%, complaining about the size of the image.
Again, no real help on Google. I read something about that you could run into trouble if you made modifications to the ROM - my phone is NOT (yet) rooted, everything as I got it, I updated everything there was to update.
Kies suggested an emergency recovery. I tried that. It stopped at like 80%, leaving me with a phone I couldn't even get into recovery mode. Kies suggested emergency initialization - meaning that all data would be lost. Nah, I wasn't that desperate yet - download mode was still working!
After some thinking I decided to flash that thing myself. I got Odin and the current firmware (I decided to go for 5.0 right away) from SamMobile (I checked the exact version of my phone under the battery pack and selected "Germany" as a country), unzipped the file, and started flashing. Some minutes later the installation completed, the apps were updated and my phone back to business. No loss of data.
Thank you, Samsung, for nothing. The only reason I could think of that might have caused this issue is the regional differences. I am using the phone with a foreign SIM card, in a foreign country - probably a wrong ROM was selected by the general Samsung update process. Somewhat embarrassing...
If you run into update issues with your Galaxy S5, consider flashing with Odin right away. Might save you some time and energy.