Complexity of "Fast Poisson Disk Sampling in Arbitrary Dimensions"
I have just implemented this algorithm, generalized for an arbitrary number of dimensions. You are absolutely correct in your suspicions about the exponential growth with $n$, as far as I see.
Each of these $2 N - 1$ iterations require a lookup in the neighbourhood for each candidate, and the neighbourhood scales up exponentially with the dimension: from a line to a square to a cube, etc. A more accurate implementation can slow this growth by excluding the corners of the hypercube in higher dimensions, since they don't fulfil the distance criteria, but it won't stop the exponential growth.
Increasing the $k$ for the higher dimensions, on the other hand, does not make much sense to me. $k$ are the candidate points to be tested for acceptance, so if you find at least one valid point among them, the algorithm will continue until the entire space is filled. If anything, I think it's easier to find a valid point for a higher-dimensional case, since there are more degrees of freedom.
Also, here's a link to my implementation: https://github.com/diregoblin/poisson_disc_sampling