Giving it some more thought and after some online research, I think I have a clearer view on this:

We should separate two things: algorithms and programming techniques. Algorithms like "to solve ax = c for x, divide c by a" have nothing to do with programming techniques. It's a way humans are used to think about "stuff to do" in "steps". Our computers are designed this way - no matter what language / paradigm you use, down bottom it compiles to some sort of machine code, which is inherently procedural and linear. Turing machines, the universal model of computation, are as linear as you can get.

OTOH, programming techniques like functional, logical and OO are just different ways to *implement* algorithms. Some of the repliers raised the issue of different (non procedural) representation of algorithms. That's curious, but still probably less useful to people, who are "designed" to think in a procedural way about solving problems.