k < 79*n + C.

Let d >= 3.
Let A be the total number of non-hut tiles that, going only by size, based on the huts and the stones below k/2^d, could border a hut or a stone of size k/2 or smaller.
Let P1 be the set of non-hut tiles that are at least 3 tiles away from a hut and that could border a stone below k/2 but not below k/4.
Let P2 be the set of non-hut tiles not bordering a hut that, going only by size, could border a stone below k/2 but not below k/8.

In my k < 86*n+32 argument, I calculated an upper bound of A < (12d-4)*n + (2d+1)*k/2^d + C.
Analogously, we can approximate A-|P1| < (12(d-1) - 4)*n + (2(d-1) + 1)*k/2^d + C, and the same with (d-2) for A-|P2|.
For d=5, this means
A < 56n + 11k/32 + C;
A-|P1| < 44n + 9k/32 + C; and
A-|P2| < 32n + 7k/32 + C.

Since each tile in P1 can't border stones or huts below k/4, it must itself be above k/2.
It's easy to see that since any neighbouring stone in P1 must be smaller or greater by at least k/4 and if a stone was surrounded by two smaller stones in P1 it would be greater than k, at least one of every 4 adjacent tiles in P1 must remain empty, which implies that
k < (A-|P1|) + 3/4*|P1| + 6+1, i.e. for d=5
k < (44n + 9k/32 + C) + 3/4*(12n + 2k/32 + C) = 53n + 10.5k/32 + C, which simplifies to
k < 79n + C.

I'm confident in a similar, but more complex, argument that at least |P1|/3 - 6 tiles in P2 must remain empty, which drops the upper bound to 77n + C.
I conjecture, but have no argument, that at least 3|P2|/8 - 6 tiles in P2 must remain empty. This would drop the upper bound to 66n + C (using d=4 instead of d=5).

There are, however, other ways to lower the upper bound which appear to be more sound: The upper bound for A assumes that stones between k/2^(d+1) and k/2^d be placed outwards from the huts' combined auras, but the stones between k/2^d to k/2^(d-1) be placed between the huts to connect them. Since d can be chosen, we can look at several values of d at once and find a common upper bound that corrects for these contradictory assumptions.