Where are places other than HKEY_CURRENT_USER\Console that cmd.exe stores colors?

This looks to be a change in Windows 10 vs. the behavior described by @JosefZ for Windows 8.x.

The 2 shortcuts executed for WinKey+X Command Prompt exist in the same place, with the same names (01 is the Admin one):

C:\>dir /b %LOCALAPPDATA%\Microsoft\Windows\WinX\Group3\*command*.*
01 - Command Prompt.lnk
02 - Command Prompt.lnk

However, running/customizing either WinKey+X Command Prompt no longer saves the console options to the HKCU\Console registry, but rather saves them (only) to the .lnk shortcut itself.

The solution in this case is to navigate in Windows Explorer to C:\Users\<user>\AppData\Local\Microsoft\Windows\WinX\Group3 and, for each of the two .lnk shortcuts, right click, select Properties, click the Colors tab and fix the colors. Or, simply replace the default .lnk shortcuts with a cmd shortcut that you have set to the right color scheme already.

Values under HKEY_CURRENT_USER\Console store default command prompt settings. However, anyone can customize appearance of different command prompt windows launched from different shortcuts; settings are stored in subkeys of the HKCU\Console registry keys: see full description in console-window-name Technet article.
A particular subkey is updated when you change corresponding shortcut properties (tabs Options, Font, Layout and Colours). The same for currently open command prompt window properties (not defaults) on window top border right click.

Shortcuts for command prompt launched via WinKey+x could be found here: %LOCALAPPDATA%\Microsoft\Windows\WinX\Group3

For instance, on my Windows 8.1:

==> dir /B "%LOCALAPPDATA%\Microsoft\Windows\WinX\Group3"|find /i "Command"
01 - Command Prompt.lnk
02 - Command Prompt.lnk

==> reg query HKCU\Console |find /I "\Console" |find /V /I "PowerShell"
HKEY_CURRENT_USER\Console
HKEY_CURRENT_USER\Console\%SystemRoot%_System32_cmd.exe
HKEY_CURRENT_USER\Console\01 - Command Prompt
HKEY_CURRENT_USER\Console\02 - Command Prompt
HKEY_CURRENT_USER\Console\Command Prompt
HKEY_CURRENT_USER\Console\Command Prompt X

==>

Here individual HKCU\Console subkeys correspond to next command prompt shortcuts:

• %SystemRoot%_System32_cmd.exe: WinKey+rcmd /D or (not sure) WinKeycmd
• 01 - Command Prompt: WinKey+xCommand Prompt (Admin)
• 02 - Command Prompt: WinKey+xCommand Prompt
• Command Prompt: shortcut from Start menu search (WinKeyCommand Prompt) pinned to taskbar
• Command Prompt X: special shortcut on my desktop.

Edit with respect to tmsimont's comment: maybe that there is a mistake in my pristine description and when you run a particular shortcut, then corresponding subkey is not created and defaults are used for launched command window…

However, a particular subkey of the HKCU\Console registry key is created/updated when you save changes to corresponding shortcut properties (tabs Options, Font, Layout and Colours). The same for currently open command prompt window properties (not defaults) on window top border right click.