Also not an answer, just a hint on how the GAP code can be made a bit faster, for future reference: GAP actually "knows" the character tables for the alternating groups. For some reason I don't know this is not used here, but we can ask GAP directly for that character table, bypassing all computations in groups, to get a faster computation, like so:
Phenomenon:=function(n)
local ct, irr,r,L,i,j,k;
ct:=CharacterTable(Concatenation("A",String(n)));
irr:=Irr(ct);
r:=Size(irr);
for i in [2..r] do
for j in [i..r] do
if IsIrreducible(irr[i]*irr[j]) then
Print([i,j],"\n");;
fi;
od;
od;
end;;
for n in [5..20] do Print(n,"\n");; Phenomenon(n);; od;