It sounds like what your colleague finds distracting clutter from, what, ten feet away, you, who are inches from it, find it useful and acceptable. It sounds like you are seeing things differently.
How can I handle a situation like this?
The first thing to do is find out exactly what is irking your colleague. There is no point you worrying about keeping the desk free from piles of paper if in fact it is things stuck to cubicle walls that are the problem.
The only way to know is to ask them - something like:
You mentioned last week about being distracted by my workspace: could you describe what it is you'd like me to change?
Then shut up and take notes. It might just be one but likely there will be a few things. Write each one down. Don't argue, don't try to explain why they're there or anything like that, your goal here is to acknowledge how your colleague is feeling and understand what's causing it. When it sounds like they're done, recap your list and check you understand it (you may need to clarify, e.g. "is it all piles of paper or just the fact that this one is teetering on the edge?").
The second thing to do once you have that list is to go back to your desk and work out if and how you can help them.
- Some things will be easy - you genuinely don't need that on your desk and it can go in the bin/the file.
- Mostly, though, clutter is there for a reason. You need to work out if there is another way you do things. So if your colleague objects to you having multiple bright colours on your project planning board, chances are you won't be able to do anything. On the other hand, unsecured scraps of paper whisked hither and thither every time someone walks past your desk could easily be put on a spike or under a paperweight or in a drawer. Could you put your "desk toys" in a box when you're not using them? Could you organise your papers in piles rather than in expansive overlapping tectonic formations?
Notice that this is about what you can or cannot do that will help your colleague, not about you judging your colleague's reactions.
Finally, report back. Start with something you're prepared to do. Be realistic about it and don't overpromise - you can't guarantee that your intray will be empty by 9.15 every day, for instance. If you're not prepared to do something, make it a brief, firm, no, explain only enough to make it clear you're not just being arbitrary: "I can't take down my project plan. I need that to make sure the deadlines are going to be hit. It won't fit on the other wall.". If you can, do the tidying you've promised before you report so you're not just returning with promises while chaos continues to reign just over your shoulder.
If they are still dissatisfied, and unless they have suggestions that will work for both of you, then politely end the conversation with "I'm afraid I can't really help you further". You might suggest they request alterations to the layout - (a partition around their desk, swapping desks, altering the angle of their screen so they don't face you, etc.) Don't get drawn into organising that, though, all you need to do is make sure they know that you've done all you can and the person to talk to next isn't you.
Equally, if they are satisfied, keep your word and don't resent them for it. You're not extending generosity, you're just committing to doing something polite and reasonable.
We all have our different quirks, often incomprehensible to others. Your colleague has taken the risk of communicating directly about what can be a touchy subject. This matters to them enough for them to start a conversation about it. Take them seriously, and at least be willing to continue that conversation; make sure your response shows due respect for your colleague's needs, your own needs and the company's needs.