ADTs are part of object oriented programming, but you are certainly correct that they can be used without using a full OO language. However, OO makes it easier to make a more complete ADT and to enforce certain rules for the ADT (such as construction and initialisation).
Using C++ does not necessarily mean extra overhead - it depends on how you use it. With a modern compiler, the overheads are minimal or non-existent if you disable RTTI and exceptions. If you use RTTI and/or exceptions, then their cost depends on the compiler, the target, and the cost of *not* using them.
It is certainly the case that what looks like a simple variable declaration or initialisation can actually be large and slow if it involves extensive constructors and class hierarchies. But the same applies to constructors like your "newSomeStructure()" - it looks like a simple function call, but there is no way of knowing how much work it will take.
I must admit to preferring C for most of my embedded work, however - it's a lot easier when you need to work at lower levels (for example, the generated assembly is much easier to follow without name mangling).