Você pode fazer uma seleção retangular e depois escolher a ferramenta de seleção de movimento. Pressione o botão direito do mouse e gire o retângulo.
No Paint.net, é possível selecionar uma área quadrilateral com faces diagonais? Como?
Você pode criar uma nova camada. Use a ferramenta Linha para desenhar uma área fechada. Em seguida, use a ferramenta Magic Wand para criar a seleção. Mudar para a sua camada anterior e você tem sua seleção
Não é algo embutido, mas pode haver um plugin que faça o que você quer (ou uma boa aproximação - veja o comentário do Ivo).
Os plugins podem ser encontrados no fórum de plugins do fórum do Paint.NET