What does a ~$ in front of a file name in finder denote

Those files look like the temporary files created when you open a Word document in Windows. The file is there as part of the recovery file that gets created in Word incase the computer was to crash before you close Word. Then the next time you open Word, the file would be recovered. When you save the file and close Word, the file is deleted. However, I have witnessed sometimes in Windows if you save a file to another location with a different name, that temporary file can somehow get orphaned, and remain on the disk where the file was opened from originally. If these names resemble some Word files you currently have and they are up to date, then deleting these temporary files will not hurt anything.

I'm still not sure whether you only see these extra items in Spotlight or in the Finder, but apparently it's the latter. Regardless of how the files got there, if you can't open them, they're useless, so you might as well delete them. I suspect they are all empty.

Rebuild the Spotlight index. If you try to search now, there will be an indication that indexing is in progress.

"All My Files" is a Spotlight search, not a folder. If you locate the files in the Finder, do they have the right name?

Given that the all caps, DOC, is an old Windows thing, they may be orphaned temp files from when they were on a windows system.

Those files are all the same size and are all too small to be valid Word files. I don't know how they got there, but it happened three years ago.