Can a paper proposing an algorithm use pseudocode only (and not a high-level mathematical description)? If it greatly simplifies the explanation, is it possible to present an algorithm in a paper without a high-level mathematical description but simply with pseudocode and very clear elaboration? Or should a high level mathematical description always be included?
I would say that it strongly depends on the target conference/journal that you will be submitting to. For instance, if you plan to submit to e.g., Algorithmica I wouldn't say that this would be suggested. But if for instance, you plan to submit on a conference that is not algo-oriented, then a high-level mathematical representation might be replaced with a detailed pseudocode along with the appropriate explanation.
But, even if this is the case, there is still the matter of

Completeness
Converging

I do believe, that you would need at least some mathematical representations in order to convince the reviewers about those two points. And in many cases, those are not THAT hard to prove, but once again, this also depends on your algorithm and your application.
So to answer your question, it is possible that you will be asked during the peer-review at least for the completeness of your approach. So I would put a bit of effort in order to justify this point.