Paal speelde in totaal 37 interlands (vijf doelpunten) voor de nationale ploeg van Estland in de periode 1920–1930. Hij nam met zijn vaderland deel aan de Olympische Spelen in Parijs, en speelde daar in de voorronde tegen de Verenigde Staten. Estland verloor dat duel met 1-0 door een treffer van Andy Straden, waardoor de ploeg onder leiding van de Hongaarse bondscoach Ferenc Kónya naar huis kon. Paal maakte zijn debuut voor de nationale ploeg in Estlands eerste officiële interland uit de geschiedenis: op 17 oktober1920 in en tegen Finland (6-0 nederlaag).