I'm not a mathematician, but I don't think that means what you think it does. It doesn't preclude being able to compute the K-complexity for some subset of strings, or for some fixed maximum complexity. Since the scenario here is checking which of a few relatively low-complexity options has the lowest complexity (eg generally could be expressed in English in <30 words), it seems it could be used in this context.