Dear Jochen, Thank you for this kind and detailed post, which summarizes my paper well. I am well aware of the literature you cite (including your own 2018 paper, which I studied in detail with an honours student), but the rules for this essay contest exclude an extensive bibliography - I cite most of these papers in my Randomness? What randomness? paper, ref. [20] in my essay, available Open Access at https://link.springer.com/article/10.1007/s10701-020-00318-8 (although your 2018 paper dropped off the longlist of references included in earlier drafts, which became almost book-length, so even in [20] at the end of the day I only cited papers I directly relied on. I will comment on your paper in a separate post about your own essay in this contest later today).
You write: "It seems to me that at the heart of this is really the observation that you can write any noncomputable function as a finite algorithm that has access to an infinite reservoir of (algorithmic) randomness." This observation is the Kucera-Gacs Theorem (this is Theorem 8.3.2 in ref. [8] of my essay (Downey & Hirschfeldt), which states that every set is reducible to a random set (acting as an oracle). Phrased in this way, your point on Bohmian mechanics ("Bohmian mechanics can play the role of the algorithmic part, which has to be augmented by an infinite random string in order to replicate the quantum predictions.") is, as you suggest, exactly the point I make in my essay, implying that precisely because of this dependence on a random oracle (which has to come from "nature" itself? or what?) it cannot be a deterministic underpinning of quantum mechanics. And likewise for 't Hooft's or any other serious hidden variable theory.
Finally, as to your last point, "that in principle the non-signaling nature of quantum mechanics should be considered as a statistical notion, like the second law of thermodynamics.": I proposed this in my Randomness? What randomness? paper but did not include it in my current essay, although all these things are closely related. In any case, as I learnt from my friend Guido Bacciagaluppi, it was Antony Valentini who first made this point, long ago. But it should be much more widely known!
Keep it up! All the best, Klaas