Great, Angel! Love the "dancespirit" site with the origins of dance-step names! Bookmarked for further study! (that could be a whole nother thread!) And it also had this to say about the origins of steps named after cities:

Mark Knowles is an acknowledged authority on tap vocabulary, having authored the
Tap Dance Dictionary, released in 1998. According to Knowles, many steps are
named after the place where they were popularized or created.
An example that
should be familiar to you is the Cincinnati (backward moving brush, hop, shuffle,
step). What you might not know (one of many arcane facts collected in his
dictionary), however, is that sometimes the Cincinnati was called Back To The Woods
because the city was covered in trees. Two other examples are the Buffalo (as in
“Shuffle Off To Buffalo”),
consisting of a brush, hop, shuffle, hop and flexion of the
opposite knee, and the Charleston, named after the city in South Carolina, where
dock workers could be seen performing a version of this movement where the body
twists while the toes move inward and then outward.


So it looks like the step was called "the Buffalo" before the popular song title added the "Shuffle Off."
Now that you know the step originated in Buffalo, all you have to do is come up with a local urban legend about it's creation...it seems you have a blank page, Angel, so go for it!

I got to researching the song at AllMusic.com and found the Dubin/Warren composition's earliest recording on a Boswell Sisters album (jazz) dated '31, which is a bit peculiar because the film wasn't released until '33.
Here's a site with the complete lyrics and credits. There is actually, also, a British version where they changed two words, panties and scanties to clothesies and thosesies. Panties and scanties a bit too risqué for you Brits back then? Hmmm, ya wouldn't know it now, would'ja? http://www.harrywarren.org/songs/0460.htm

"Shuffle Off to Buffalo" was also the title of a Merrie Melodies cartoon released in '33. (taken from the song title)

Now off to find the year and creator of the step...shufflin' off to, guess where?....who knows?....