For example, the Itanium C++ ABI (http://mentorembedded.github.io/cxx-abi/, perhaps Itanium's only real legacy) adopted by Linux/ELF and other platforms, leaves a huge amount of fingerprints on a binary. It'd take a very conscious effort, including hand-crafting linker scripts, to generate a C binary that a tool would incorrectly think was C++.
Back in the 90's there was one targeted specifically to executables produced by Borland compilers.
Once you get some C code that does things with structures and function pointers like a C++ compiler would do, I think it's not impossible to turn those back into classes if you can recognise the patterns that a C++ compiler uses to compile C++ constructs like classes, virtual functions, etc.
I'm afraid that hasn't been true for a number of years. Turn on the optimizer and the resulting assembly can be totally unrecognizable as a translation of what you actually wrote. The compiler takes all kinds of steps both to eliminate redundant operations (via CSE, loop unrolling, etc.) and to take advantage of the weird quirks of modern CPU architectures, like out-of-order execution.
printf(...);
for (...) {...}
The printf never executed. So I fired up gdb and confirmed the segfault was happening where I thought it was, but the for loop was being initialized before the printf. Even with debugging on and optimization off. Could be a bug in clang (I didn't think to try it with gcc), but even so it shows that the way things should work in theory don't necessarily dictate the way they do work in practice. class data fields -> structure members
non-static methods (ctors/dtors included) -> functions with an extra 'this' pointer parameter
inheritance -> extended structures with matching prefices
virtual functions -> structure with function pointers
operator overloading -> methods with special names
default arguments -> automatically inserted by compiler
function overloading -> types encoded in name of function
templates -> whatever code they generate
exceptions -> special library functions are used, e.g. _CxxThrowException()
Some of those don't decompile so well (e.g. template-generated code, although a refactoring tool might be of help), and things like operators and overloaded functions are probably more of a stylistic choice than a difference in the generated code, but for the most part it doesn't look impossible to get some C++ features to show up in decompiled code. (And given that many of the C++-level optimisations revolve around removing unnecessary code, they could make the C to C++ step even easier.)