Tentative answer to my own question. Please criticize!
All variables in capital are one 128-bit word, with $w=7$. Parameters are as in the question, and $k-4\le n\le128$.
I use an auxiliary arbitrary public permutation $\large\mathscr P$ of one word; a simplistic one is constructed using Addition-Rotation-Xor. A function evaluation goes:
- set $D$ to the function's input
- memory setup: repeat for $C$ from $2^{k-w}-1$ down to $0$
- write $D$ to memory at address $C$
- set $A$ to zero.
- main loop: repeat for $C$ from $2^n-1$ down to $0$
- set $A$ to $A\oplus{\large\mathscr P}(D\oplus C)$
- read $R$ from memory at address $A\bmod2^{k-w}$
- write $D$ to memory at same address
- set $D$ to $D\oplus{\large\mathscr P}(R\oplus C)$
- output $D$.
Some rationale of the design:
- Address of the next memory location used depends, thru two nested invocations $\large\mathscr P$ and depending on chronology thanks to $C$, on the value previously read $R$, and will-be result $D$.
- The main loop has reversible effect on the combination of memory, $A$ and $D$; hence the input-to-output entropy loss can be estimated as at most 0.8272… bits.
- Mixing of counter $C$ makes getting into a short cycle unconceivable.
- The average number of accesses to each memory cell is at least 8.
Permutation $\large\mathscr P$ is:
- set $X$ to the function's input
- repeat for $t$ each of the six constants 3, 5, 7, 13, 23, 43
- set $X$ to $3\big(X\oplus(X\operatorname{\lll}t)\big)\bmod2^{128}$ where $\lll$ is left rotation on 128 bits
- output $X$.
Note following comment: this is a toy/simplistic permutation, not to be reused outside the present context of deep iteration, and was not the focus of the answer. There are far less rounds than necessary for complete propagation of a bit difference; but in the context, two invocations (thus twice more rounds) are nested from $R$ to $A$. Zero is a stationary point, since the only constants are rotation counts (hastily obtained by starting from 3, doubling, and rounding down to the next prime).
Tentative test vector: for ${\large\mathscr P}\big({\large\mathscr P}(1)\big)$ I get 0x5be8f27af383369a91de3e614e6650dd
.