This difference is possibly because the data is pushed to the CPU for the indexing step, which is possibly because the index lives on the CPU. I say this because pushing the data to the CPU before indexing gives comparable times in the two cases:
import torch
from time import time

print('Torch version {}'.format(torch.__version__))


def test_conv_timing(K):
    print('Kernel: {}'.format(K))
    x = torch.randn(1, 512, 160000, dtype=torch.float32, device='cuda')
    kernel = torch.randn(512, 1, K, dtype=torch.float32, device='cuda')
    for i in range(10):
        dummy = torch.nn.functional.conv1d(x, kernel, groups=512)
        x.to('cpu')        
        start_time = time()
        idx = torch.randint(0, 512, (1,))
        y = x[:, idx, :] 
        # This y lives on the CPU. To get the same effect as the original code  
        # we should push this y and the x back on to the GPU.    
        print('{} elapsed time {}s'.format(i, time() - start_time))


test_conv_timing(K=5)
test_conv_timing(K=20000)

This is surprising to me since I would expect Torch to throw an exception if it is asked to do an operation involving entities which live on different types of processors. I guess here the implementation does the back and forth transfer silently in the background.
I haven’t checked the documentation; this may be explicitly stated somewhere.