Flames are not the same as fire. Flames are the gaseous part of a fire while embers are the non-gaseous part of a fire.
Some fires consist of only embers, some of only flames, while others again consist of both embers and flames. Whether the flames or the embers appear first or at all depends on what is burned. On average embers produce more smoke than flames do.
That Smokey the Bear was able to find a fire before the flames simply means that he was able to find a fire that consists of only embers.
What the idiom is actually saying is that "there is no smoke if there are neither flames or embers", or said in another way "there is no smoke if nothing is burning".