Okay, as I understand the story so far, you're back to having a working iPhone but your missing the apps you purchased (for free or paid) from the App Store, and the backups aren't restoring them.
One word: relax.
Your apps aren't gone. If you only backed up to iCloud, then iCloud only has a *list* of all the apps you purchased -- it doesn't physically back them up, since that's redundant (and would take up much more space then the 5GB you probably have).
I had to do this once, and at first it didn't look like any of the apps were there either, but overnight, a number of them reappeared -- as dimmed icons with circles filling in at first (which I later realized was downloading) and then eventually most of them came back. Maybe that's what is going on with yours, and it just takes a lot of time because it is (stupidly) trying to download all the apps at once.
But even if that isn't what's happening, again I say "relax." If you have the basic system and the default apps, then you have the App Store. Sign in (if needed), go to "Purchased," select an app (just one for now) and re-download it. See how that goes. Then do the rest of them.
You may (or may not for Game Center games) lose any high scores or stuff like that, but the apps will return. As Charlie said, there might be one or two that don't because the app has been pulled because the developer never updated it for higher than iOS 7, but most apps are well-supported so I'm sure you'll get nearly all of them or all of them back over time.