They probably entered the Brazilian grappling scene through Luta Livre which got them from catch. They almost certainly entered the US and Europe scenes through Japanese shoot wrestling, which in turn got it from catch through Karl Gotch or Billy Robinson.
I have never seen any documentation of heel hooks being used in Judo or pre-Kano Jujutsu. It's possible Maeda or one of the other Judo/Jiu-jitsu instructors in Brazil learned them from their cross-training in catch (either in Europe or the Americas) and passed it along to their students. It's possible that the heel hook wasn't imported until generations later in the Luta Livre-GJJ rivalry.
If you go a couple generations back in the lineages of non-Gracie Brazilian jiu-jitsu schools, you see a lot of references to so-and-so being a great leglocker. However, that seemed to die out around 30 years ago, and I haven't seen clear mentions of heel hooks being used in particular. The matter is complicated by the tendency of Brazilians to refer to ankle locks, toeholds, and heel hooks collectively as "footlocks". Practically speaking, this makes it impossible to determine whether any of these older masters used heel hooks and if so where they originally learned them. It's possible, and I speculate that this is the case, that heelhooking had all but died out in Brazilian jiu-jitsu before the re-exposure to it through Pancrase/Pride/etc. I may be entirely off-base on that though.
If you look at the modern popular leg locker pioneers, they largely acknowledge two primary sources for their material: Japanese shooto and sambo. Eddie Cummings credits Bodycomb, Krishna Mirjah, and shooto. Bodycomb credits sambo and shooto. Krishna Mirjah acknowledges shooto. Scott Sonnon (love him or hate him) acknowledges sambo. Daisuke Yamaji hasn't publicly spoken on the matter to my knowledge but my friend who trains there has heard him mention shooto. Danaher doesn't seem to want to credit anyone beyond a cursory thanks to Dean Lister but we all know that leg locking didn't take off in his team until Cummings joined it. Dean Lister credits sambo, Luta Livre, and a little shooto. The Machados seem to mostly credit sambo.
(I use "shooto" in the above as a catch-all term for Japanese shoot wrestling based on catch. It is not always the most accurate term but you get the idea.)
And then sambo itself took a ton of its leg locks from catch wrestling! So really, it all seems to go back to catch through a few steps removed.
Summary: I've seen almost no reason to think that the modern use of heel hooks owes anything to Judo or older Jujutsu styles. On the other hand, there are a lot of reasons to think that it derives from the influence of styles descending from catch wrestling.