There is no mandate for the upper levels of government to dictate which solutions are being used on a local level. Combine that with need for tendering on every single solution and you've got a big mess of small companies underbidding bigger companies that could unify the software landscape and instead build a cheaper, small solution that has zero interoperability with the neighboring municipality.
The need for fax et.al. is not because people don't know how to use computers, but because there's thousands of applications fulfilling the same exact job, but are incapable of talking to each other. Paper is currently the only compatibility layer that works everywhere.
There are ongoing efforts to provide a common data exchange format (technical working group) as well as redesigning how the software for government is being build (tendering processes, public money - public code movement, et. al.)
German government is currently incapable of doing its job in a way that is legally required, missing deadlines and not providing citizens with the services that they are entitled to because they are unable to manage the workload due to the paperbound processes. There is zero fear of humans being replaced by machines. It's rather that more and more humans are leaving government due to burnout.
I find myself chuckling a little at this, because this is a common excuse for things being slow moving (or just wildly inconsistent from place to place) in the US. It's somehow comforting to know that countries of all size and population that are organized like this will still have the same problems.
To be fair, though, the US and many decent-sized municipalities do actually have a pretty good digitization story. I'm actually having trouble thinking of routine government-related things that have to be done in person... or even by mail. I guess you have to send mail to apply for or renew your passport (though the State Department already has an online form that fills out a printable application for you). And you have to go in person to get a marriage license (but I think that's a feature, not a bug; and hopefully that's not a routine activity, anyway). I had to do an interview to get my Global Entry (eliminates most of the wait at immigration when re-entering the US) thing approved, but the application process was all online, and my recent renewal was completed from my couch.
Otherwise...? I've set foot in a DMV perhaps 3 times since I moved to California 19 years ago (once when I first moved, to take the written driving test; once when I lost my driver's license and had to prove who I was to get a new one; and once when I had to apply for the ridiculous new "REAL ID"). I file my income taxes online, and whatever money I'm due or owed gets electronically transferred. I pay my property taxes online. I activated the electric and gas utility service (not quite government, but adjacent) online when I last moved. Mail forwarding when your address changes is done at the Postal Service's website. I even signed all the paperwork to buy a new home online (if you have a mortgage lender, they'll want some things signed in person, but they can someone to your house for that, and at any rate the government-related paperwork is all handled by a title company for you, at least where I live). You can even pay parking ticket and driving infraction fines online, if you don't want to contest them.
The online systems to take care of this stuff do all vary in clunkiness to some degree, but some of them are quite modern-looking and have decent or even good UX. The federal government even has 'login.gov' now, which they're slowly (very slowly) getting various agencies to adopt so you have a single sign-in. I don't think states and municipalities are allowed to use it, though.
The issue is that germany is deeply federated, different decisions are made at different levels. This could translate well into software by having the higher levels create interop standards and reference implementations that allow for plugins while the lower levels use the reference implementations (with plugin extensions for the myriad of special of special cases) or just implement their own according to the standard.
But unfortunately it doesn't translate because the german state either picks the cheapest contractor (which almost always leads to blown budgets and delays) or they pick by nepotism.
They are also dead set on waterfall projects and don't seem to realize that if they keep blowing budgets anyways, that might not be the best strategy.
I agree that this would be ideal, but on a local scale, these projects are easier to manage.