Good question. On the surface, it'd be obvious to recommend C++, because "it's object oriented like Java". Only problem is, it's not really true.. C++ allows OOP, yes, but it's just one of several paradigms that C++ supports. Treating C++ like a OOP language (and especially, treating it like Java) will only lead to frustration.
The problem is that Java and C++ don't actually have much in common. Java programmers often believe that Java was inspired by C++, but that's only true if by C++ you mean the very earliest versions of C++, which might more appropriately be called "C with classes".
Since then, C++ has transformed completely into its own language with its own way of doing things. It has probably changed far more since then than Java has. A Java programmer back then would still be able to make sense of today's Java code. Not so for C++. So I'd argue that C is actually closer to Java than "modern C++" is. C is what you get if you take Java and strip away the GC and the concept of classes and a few other abstractions. To arrive at C++, you have to add a similar number of features to our hypothetical stripped-down Java as well.
Further, C++ is a remarkably complicated language, and learning it well takes ages. And if you don't learn it well, you're going to shoot yourself in the foot over and over again.
Finally, it depends on your objectives.
C++ is a much more modern language than C, and once you learn it, very expressive and powerful and, surprisingly, it can even be very elegant and concise. But the learning curve is nasty. So for native programming in the long term, I'd recommend C++ over C.
But if your goal is primarily to interface with the Win32 API (or other native API's for that matter), you won't need C++. Win32 and most other API's are written in C, not C++, and you most likely won't need very complex code to interface between that and Java in any case.
About learning Win32, you're right, all the details you need are on MSDN. If you want the big picture, Petzold is the book on the subject.