Here is the solution that I settled on in my own code after searching for this question, taking inspiration from Jorge's answer.
DataTable RemoveRowsTable = ...;
int i=0;
//Remove All
while (i < RemoveRowsTable.Rows.Count)
{
     DataRow currentRow = RemoveRowsTable.Rows[i];
     if (currentRow.RowState != DataRowState.Deleted)
     {
         currentRow.Delete();
     }
     else
     {
         i++;
     }
}
This way, you ensure all rows either get deleted, or have their DataRowState set to Deleted. 
Also, you won't get the InvalidOperationException due to modifying a collection while enumerating, because foreach isn't used. However, the infinite loop bug that Jorge's solution is vulnerable to isn't a problem here because the code will increment past a DataRow whose DataRowState has already been set to Deleted.