Everything looks good to me. I think the kata can be approved now (but I'm not able to do it myself).

Feedback after completing the kata below.
Overall, nice job. This was a bit different than anything I've seen so far (but I am still relatively new here). The test cases seemed thorough.
Possible improvements:

1. The instruction "throw an error" could be more specific, since most lua katas don't have a requirement like this. I recommend mentioning error("msg") or assert(condition, "msg") in the text.
2. I was confused at first by the instruction "Surrogates (U+D800 through U+DFFF) ... must be considered errors" until I read the utf-8 wiki page. Maybe something like "code points U+D800 through U+DFFF are utf-16 surrogates, illegal in utf-8, and should be considered errors"
3. Test error messages are difficult to interpret since they attempt to display the raw byte values as text. Maybe convert the byte string to a table of 2-digit hex strings for comparison purposes?

I think there is a typo later on the same line then: "where aaabbbbbbccccccdddddd" has 3 a's in it.

Lua translation added.
https://www.codewars.com/kumite/62e35a5d8852220069cbfde4?sel=62e35a5d8852220069cbfde4

I didn't. I modified it to use fill to discover the holes.

With Python moving to JIT, counting bytecode instructions probably isn't sustainable. I was thinking of HW perf counters, like the ones accessible by running 'perf stat' on Linux.

If codewars had a feature to run with perf counters and count the number of instructions executed, that might be a better way to restrict the solutions to something more efficient O() wise.

Yes the array insert promotes it to O(n^2), but switching from a python list to array('q') made it fast enough to pass the testcases at least.