Deciding if a wildcard string is completely matched by another wildcard string in a set
How about using a finite-state automaton? The language $S$ is finite and therefore regular. Even after the transformations below it will still be regular. So after the usual steps to convert the regular expression into a deterministic finite-state automaton, you will have a recognizer for what you want that operates in $O(k)$ time. Hopefully this idea will still be workable if there are bugs in what is proposed below.

The wrinkle is how to deal with the wildcard operator: ?. A wildcard in a wildcard string matches a 0 or 1 in a test string. But since we're trying to recognize wildcard strings, a wildcard in a wildcard string matches 0, 1, or ? in another wildcard string. This set is still regular, so we transform every occurrence of ? to the regular expression (0|1|?) where the vertical bar is the usual alternation operator. So if your whole set $S$ is {10??1, 0?1?0}, the resulting regular expression will be (10(0|1|?)(0|1|?)1 | 0(0|1|?)1(0|1|?)0)

As for adding strings to the machine, there's some recent work on changing a finite-state automaton incrementally. See this paper by Daciuk et al: "Incremental Construction of Minimal Acyclic Finite-State Automata".

Does this help?