Massive evolved stars in transition phases, such as Luminous Blue Variables (LBVs), B[e] Supergiants (B[e]SGs), and Yellow Hypergiants (YHGs), are not well understood, and yet crucial steps in determining accurate stellar and galactic evolution models. The circumstellar environments of these stars reveal their mass-loss history, identifying clues to both their individual evolutionary status and the connection between objects of different phases. Here we present a survey of 25 such evolved massive stars (16 B[e]SGs, 6 LBVs, 2 YHGs, and 1 Peculiar Oe star), observed in the K-band with the Spectrograph for INtegral Field Observation in the Near-Infrared (SINFONI; R = 4500) on the ESO VLT UT4 8 m telescope. The sample can be split into two categories based on spectral morphology: one group includes all of the B[e]SGs, the Peculiar Oe star, and two of the LBVs, while the other includes the YHGs and the rest of the LBVs. The difference in LBV spectral appearance is due to some objects being in a quiescent phase and some objects being in an active or outburst phase. CO emission features are found in 13 of our targets, with first time detections for MWC 137, LHA 120-S 35, and LHA 115-S 65. From model fits to the CO band heads, the emitting regions appear to be detached from the stellar surface. Each star with ^12CO features also shows ^13CO emission, signaling an evolved nature. Based on the level of ^13C enrichment, we conclude that many of the B[e]SGs are likely in a pre-Red Supergiant phase of their evolution. There appears to be a lower luminosity limit of log L/L_solar = 5.0 below which CO is not detected. The lack of CO features in several high luminosity B[e]SGs and variability in others suggests that they may in fact be LBV candidates, strengthening the connection between these two very similar transition phases.