Do you want the relative degree of conservation, as in the Human eEF2 protein is 76% identical to Yeast eEF2 protein while Human DNA polymerase III protein is 82% identical to Yeast DNA polymerase III protein?  (I am making up those numbers, guessing).

Or do you want to know yes/no does each class/genus/species contain a copy of the gene?  i.e. plants are lacking genes for neurons etc.

For both questions, seeking information across the entire eukaryotic tree is a bit of a problem, because other than some of the highly conserved "housekeeping" functions such as DNA replication, energy production, protein synthesis etc., there are many protein families with hundreds of members (such as serine/threonine kinases, or GTP-binding regulatory proteins) making determinations of paralogs vs orthologs difficult to impossible.  

I don't find the answer to either question by quickly poking around in the Gene Ontology project or ENSEMBL or other sites.  But I think you should ask some of the people involved in those projects.  Another useful resource would be the Enzyme Classification Commission which will help you organize your proteins into classes, so you can search to different levels in the tree with different groups of proteins.  The homeobox genes, for example are found in multicellular animals but not plants, fungi or protists.

I look forward to seeing what other answers you get.

http://bitesizebio.com/10683/understand-ec-numbers-in-5-minutes-part-i-how-ec-numbers-work/

Use Clustalw. http://www.genome.jp/tools/clustalw/ After doing the alignment you have the choice of a few phylogeny methods. 

Yes, I wanted to determine the relative degree of conservation e.g. the Human eEF2 protein is 76% identical to Yeast eEF2 protein while Human DNA polymerase III protein is 82% identical to Yeast DNA polymerase III protein?

I've got a long list of human proteins-of-interest. So manually identifying their ortho- or paralogs across various eukaryotic species and doing alignments seems a bit insane. 

I was hoping there might be an online tool with such functionality.

Re: determining evolutionary age: I have used 'ProteinHistorian' to estimate the evolutionary age of the protein set ... it's a great tool.