I'll speak from experience playing the demo. It's just like Brawl (though the base kill power of the kill moves seems quite a bit higher), but that's not so bad. If your character is good enough that spamming your only kill move is not your only option, you just have to mix it up a bit. Don't start using your kill move 15% before actual kill percent and just hit it raw over and over; you'll stale it like crazy and barely fail to kill over and over again. A lot of people did exactly that in the demo and then seemed surprised they were having such a hard time getting kills, but it can be avoided. Mix up your kill moves a bit, relying on multiple options at different times so you'll have fresh ones ready. Use things like jabs, projectiles, grab pummels, Dancing Blade, and multi-ftilt to quickly refresh moves. In general just stop and think about what you're doing as well; the stale move system is basically there to reward thoughtful play, and it's actually a very interesting skill test.
It's also kinda important to how these games are balanced in that it helps characters with a really diverse array of kill moves since staleness is just not such a big deal when you have 5 good kill moves and almost always can easily pull a fresh one. A fast character, on the other hand, probably has more limited kill options and can easily run into staleness trouble without careful play; in my eyes, that's a pretty fair way to give them different strengths and weaknesses.
As per combos, this wasn't really possible to explore in the demo, but I can say this from Brawl. Knockback and hitstun are directly proportional so, if you stale out a combo move, you keep them closer but also do less hitstun so it's not really a linear advantage. In general in Brawl, it was still usually easier to combo with stale stuff than with fresh stuff (some cgs were crazy and depended on particular careful levels of staleness; Pikachu had a lot of those in Brawl), but you were also doing less damage so it kinda worked out. I don't think this is likely to be a big problem, especially with how mindfully the parameterization seems to be in regards to things like combos.