Ich würde sagen, "eh" ist hier umgangssprachlich für "ohnehin", manchmal auch "sowieso" (fand ich jetzt nicht sooo falsch). Meist passt da anyway ganz gut.

Did you know that anyway?

usw.

Macht die Verbindung von Vergangenheit und already vielleicht Sinn?

In welcher Gegend werden denn solche Fragesätze mit "eh" gebildet? Für mich klingen sie ein wenig seltsam. "ohnehin" oder "sowieso" dürfte aber passen.

@ Dragon: In Österreich und Süddeutschland. :-)

Hm, 'ohnehin' ist ganz gut, in Sätzen wie
'Er ist eh schon da.'
oder ähnlich. Aber in den Fragen passts trotzdem nicht ganz.

Hast du die Rechnung eh schon bezahlt?
bedeutet zB: sie hätte bereits bezahlt werden müssen (also die Deadline liegt in der Vergangenheit), und es wird impliziert, dass die Bezahlung auch bereits abgewickelt ist, eine Art Vertrauensvorschuss an den Gefragten, sozusagen. In diesem Satz würde ohnehin nicht nur was anderes heißen, es heißt meiner Meinung sogar garnichts.

Did you already pay the bill?
scheint mir hingegen eher eine völlig neutrale Frage zu sein - entspräche also dem Beispielsatz ohne eh.