com xmlstarlet :
xmlstarlet ed -d '//Placemark[.//tessellate]' < myplaces.kml
E como kml usa namespaces, você precisa defini-lo primeiro (consulte a documentação do xmlstarlet )
xmlstarlet ed -N 'ns=http://www.opengis.net/kml/2.2' -d '//ns:Placemark[.//ns:tessellate]'
Com perl , você precisaria processar o arquivo como um todo (não linha por linha) e adicionar o s flag a s/// . E mesmo assim, mesmo com correspondência não desejada, ainda corresponderia do primeiro <Placemark> até o próximo </Placemark> que ocorre após o próximo <tessellate> . Então você precisaria escrever algo como:
perl -0777 -pe 's|(<Placemark>.*?</Placemark>)|
$1 =~ /<tessellate>/?"":$1|gse'