The obvious thing would be to use torch.multinomial(torch.ones(n, d), 4), which would take out ~1/3 of the time for me but is somewhat slow.
I can half the time (relative to your code, on my machine, on CPU etc.) by using rand + topk.
    sample = torch.rand(n, d).topk(4, dim=1).indices
    mask = torch.zeros(n, d, dtype=torch.bool)
    mask.scatter_(dim=1, index=sample, value=True)

I imagine for k much smaller than d you could be blazingly fast writing your own GPU kernel that just loops until it has found four new things because the 37700 is just one giant opportunity for parallelization on the GPU.
Best regards
Thomas