Test in Microsoft Whiteboard or Paint
Rest your palm on the screen.
Hold the Surface Pen a few millimetres above the display.
Move the pen up/down without touching.
If the unwanted marks appear there too, it establishes this as a system-level pen/digitizer problem.
These are workarounds, not a fix. If the problem is in the digitizer firmware, none may fully solve it.
Pen & Windows Ink settings. In Settings → Bluetooth & devices → Pen & Windows Ink, turn on "Ignore touch input when using my pen" if it's off.
Disable the touch layer while you draw. In Device Manager → Human Interface Devices, right-click "Intel(R) Precise Touch Device" and choose Disable device. You lose finger touch until you re-enable it, but if the phantom dots come from palm contact being misread as pressure, this should stop them. It's the most promising test, and it's easy to reverse. A disabled touch screen also means you can't use finger gestures to pan and zoom in your art apps.
Switch input API in Photoshop. Photoshop has a Windows Ink / Wintab toggle in Preferences (the location varies by version). Since both of your apps may rely on Windows Ink, testing the other API could show whether the fault is in that layer.
If this is your new Surface Pro 12, I would also push for a hardware replacement/escalation rather than spending more time reinstalling Windows.