I'm far from an expert but I'm happy to pass along what little I do know...
The real core of your question is "how can I get beyond this plateau?" Everything else is just details.
The standard rule of getting past any plateau is try something different. Walking is terrific, but it sounds like that is your only mode of exercise. The trouble with that is that you get good at it! As you do one exercise more and more, your body gets more efficient at it. Bodybuilders always talk about the concept of "muscle confusion" -- doing a bunch of different exercises to exert the muscle in a bunch of different ways, to make it strong. The same idea holds here -- you should be training your body in more than one way.
One specific recommendation I would make is do some strength training in addition to your walking or cardiovascular routine. This doesn't need to be weight training to build big muscles, but you need to make sure all the muscles in your body are in good strong condition. There are three big reasons to add strength training:
- Better fat burning. When you do cardiovascular exercise (including walking), your body is using muscle tissue to burn fat. Having more muscle tissue (or just muscle tissue in better condition) will help your body burn fat better.
- Improved appearance. You mentioned having excess belly fat. I don't know the details of your situation, but could your real issue be how the belly looks versus the actual amount of fat that is there? Perhaps the issue is that the abdominal muscles are hanging loosely, and having good tone in the abdominal muscles would greatly improve the appearance.
- Good body mechanics. Good strength and flexibility are always important just to make sure your body is well balanced. Without these, you can start to develop bad habits with posture and sitting (I know I did!) that turn into problems later on. Prevent that now.
I would recommend basic body-weight exercise, with a focus on 1) having strong and stable core muscles and 2) making sure your lower body (those muscles you use for all that walking!) have good strength. I would recommend just basic planks, pushups, squats, and lunges. No weights needed, just do everything with your own body weight. And, as I was saying, do lots of different exercises; keep mixing it up.
About those details...
Why is all the remaining extra weight concentrated in the belly?
Per my notes above, one possibility is that it just looks that way. But if you Google "body fat types" you'll see lots of discussions about how different people store fat in different ways (the "thyroid" body type, the "pituitary" body type, etc). I'm nowhere near convinced that there is good science behind this, but I absolutely have seen how different people store body fat in different ways, and "primarily storing fat in the belly area" is certainly one of those. Perhaps that is just your body type.
Is it possible that all my walking caused me to lose a lot of muscle and not a lot of fat?
Doubtful, unless there is some medical problem. (I am certainly not a doctor, so please don't construe this as medical advice.) If you've been doing walking and no strength training, then you've certainly been doing nothing to keep muscle, and it's certainly possible that you lost muscle during the process. But it's most likely that you've lost more fat than muscle.
How do I get below that 80kg plateau?
I would strongly recommend that you worry less about the total body weight and worry more about body fat. If your weight remained stubbornly at 80kg but you lost all your bodyfat you'd still be happy, yes? (If your answer is "no", then skip the doctor and personal trainer and go find yourself a psychiatrist ;-) So instead of a simple scale, I would suggest just using the mirror as your guide or, if you prefer to think about numbers, then get a body fat monitor scale or some other way to assess total body fat. This isn't about weight. It's about fitness.
Phew, for someone who knows only a little, I sure did say a lot... Best of luck to you.