I deleted the program and all files & folders I could find
Why should a file exist, which you have deleted before?
Do I have a problem or do I just create the file
Just create it and everything is fine. ST merges all *.sublime-... files it can find together and working with the resulting content. So if you did not change any settings, there is no need for a /Packages/User/Preferences.sublime-settings so far.
You can use Main Menu > Preferences > Settings to open a side-by-side view with all default settings on the left and a blank file on the right. Saving the right one will automatically create your missing file.