$str =~ /^(?:[^:]|::(?!:))*\z/

Which means $str consists only of characters other than colon ([^:]) and pairs of colons not followed by more colons (::(?!:))