I have Thunderbolt 3 cable (verified), but it didn't work as well. I also checked multiple USB-C ports on MBP because I suspected it might be the problem of providing port. Not sure if Stream Deck has battery, as it can be used only through wired connection and it doesn't have any memoized features, yet I think you might be right with your guess. I found somewhere that I need USB 3.1 gen 2 cable, and that's what I ordered, but based on Amazon description I don't really trust it's going to work.
The whole issue is something that IMO should be dealt with by manufacturer. For ordinary customer this is a problem with a landfill solution.