What does trade deficit really mean? I watched a video about how if America imports USD 1m worth of goods but only exports USD 600k worth of goods, there is a USD 400k debt to other countries if the other country allows this deficit.

US importers pay for the value of the goods they import. So why is there debt? Doesn't the US pay in USD the full value based on the transaction? Why would importing have anything to do with exporting, also why would anyone "exchange" goods for credit with somebody that already is USD 18 trillion in debt?
Every country has a trade balance, which is defined as exports minus imports. The United States is a typical observing state, which means their imports are higher than their exports. I do not know the current numbers but USD 1m of imports and USD 600k might be right. In this sense you import USD 400k than you export. 
Now as you already pointed out you have to pay you imports in USD. Now the point NickJ mentioned is insofar important  as to understand what you are actually entitled when holding USD. And all you are entitled to is to buy products within the United States. True, you as a single person could change it into another currency, but this does not change the fact that some else is holding USD and is sooner or later going to demand goods in USD.

So it is correct that in some sense running a trade deficit really brings debt to a country. 

However, one has to understand that running a trade deficit is not only indebting. In some way it is a credit for future production and consequently employment. The debt you are causing when running a trade deficit can also be seen as in some way storing demand for US products which in some point in the future will be carried out.