Japt, 44 bytes
m£Z¯Y cZtY2 Ô cZsY+2Ãrc
Try it online!
It times out on the first test case because it's super inefficient (something like O(n^n)?) but it should be a viable algorithm. Input is weird; it is a singleton list containing the input, but the input itself is formatted as a list of upper-case characters. I think that would typically be valid, but if not let me know.
#Step 1: try all the swaps
m #For each string Z reachable with n swaps (n starts at 0)
£ Ã # For each letter Y in Z:
Z¯Y # Get the letters before it in Z
c # Concat
ZtY2 Ô # Y swapped with the following character
c # Concat
ZsY+2 # The rest of Z
rc #Flatten by one level
#Result: A list of all strings reachable with n+1 swaps
#Step 2: Check for "VK"
®¬ #For each string from Step 1:
ø"VK" # Check whether it contains "VK"
#Result: A list where 1 indicates there was "VK" and 0 otherwise
#Step 3: Increment the counter appropriately
W+ #Increase the counter by
VÌ #The value for the original string when run through step 2
#Result: 0 if 0 swaps were required, the current number of swaps otherwise
#Step 4: Iterate or end
Ve ? #If all the reachable strings contain "VK"
ß # Repeat the program with the current values
:W #Otherwise return the counter
#Result: Outputs the counter when a non-"VK" string is found.