I have no first hand knowledge of the history of West Yellowstone fly shops, but I've read a couple of things that might be clues.
In the Martinez biography in Trout Country Flies, Bruce Staples writes that Martinez started spending summers in West Yellowstone by 1932 and "Here he established Don's Tackle Shop in the Totem Cafe" Mike Valla also has a chapter on Martinez, in The Founding Flies. There is a picture of Martinez in his shop and the caption says: "...(which eventually became Bud Lilly's fly shop)."
The Pat Barnes biography in Staple's book says that Barnes tied for Martinez, then was in the 8th Army Air Force during WWII then opened Pat Barnes Tackle Shop and Guide Service in 1946.