Could we detect GMO foods if there were no samples to compare with?
[G]iven two potatoes, one GMO and one natural, would you be able to detect which is which without having any samples or knowledge about what parts of DNA to consider engineered by humans?


No, you can't distinguish them without knowing a priori the DNA sequence of the wildtype and of the GMO. There is no other mark left within a GMO in the general sense. 

Of course, one particular GMO is created with one particular goal in mind. One particular phenotypic effect. If you detect the phenotype of a GMO, then you can recognize it. For example, if you make a GMO tomato that produces a new type of pigment, you can, of course, recognize it by the presence of this pigment! However, there is no general attribute of being GMO that you can recognize. You need to look for something specific that you know about a specific GMO (or specific wildtype).

There are also phenotypic traits that you find (quasi) exclusively in GMO such as Cytoplasmic Male Sterility (CMS) for example. If you find CMS in a plant, then you can be pretty sure it is a GMO. But if you can't find CMS though, you can't be sure it is not a GMO.