とりあえず削除するほうはこんな感じでできました。SQLのように一気に削除することはできないので、1件ずつ削除していくことになります。
$list = $context.Web.GetList('/Lists/List1')
$query = New-Object Microsoft.SharePoint.Client.CamlQuery
$query.ViewXml = @'
<View>
<Query>
<Where>
<And>
<Eq><FieldRef Name="ColumnA" /><Value Type="Text">白菜</Value></Eq>
<Eq><FieldRef Name="ColumnB" /><Value Type="Text">東京</Value></Eq>
</And>
</Where>
</Query>
</View>
'@
$query.ViewXml
$items = $list.GetItems($query)
$context.Load($items)
$context.ExecuteQuery()
foreach ($item in $items) {
$item.DeleteObject()
$context.ExecuteQuery()
}