Sería así:

re.match(":(.+?):",n)  

El mismo código en perl:

use v5.16;
 
$_ = ":hola soy-una cadena : con : je";
 
/:(.+?):/;
 
say $1;

? en las expresiones regulares se usa para indicar un caracter que puede o no aparecer o, como en este caso, para seleccionar la menor cadena que encuentra ya que por defecto la expresión regular coincide con la cadena más grande que encuentra.

Saludos!