For a typical users use case, I bet you could downscale the image 16x (using the GPU, and therefore very fast), flood fill on the much smaller image (using slow javascript over each pixel), then expand the image up to the original size and reprocess just the border pixels (and there aren't many border pixels compared to the total filled area).
This method might not produce perfect results when the paint can 'escape' through a tiny gap that isn't visible on the downscaled version... But at the same time, I suspect most users don't actually want the paint to escape through a tiny gap, so that might be the right behaviour.
You wouldn't upscale, you'd fill 16x16 blocks in original image iterating over downscaled image and if the block wasn't all the same color you'd process it normally. In fact you don't need to flood fill in downscaled image, just do edge detection.
Been a long time since I was a kid playing with Deluxe Paint, but "fill except where I missed a tiny gap" would have been exactly what I wished the fill tool would do! I don't think I've used a fill tool in earnest since :-(
https://en.wikipedia.org/wiki/Flood_fill
I was hoping the author had figured out some clever solution involving some implementation detail of HTML Canvas.