What determines a substance's energy of activation with air?
Energy of activation is pretty much an experimental thing. You can try to explain obtained results, but predicting exact values without numerical analysis is not really possible.

Basically, given a compound to react with air, you first devise a reaction mechanism -- how the reaction proceeds. Now, using some rules, you determine the highest energy transition state. Finally, you try to approximate the energy difference between this and the reactants by comparing with known quantities.

About the rules that are used to compare energies and energy differences: There are many of them, and out of the scope of this answer (indeed, one would be hard pressed to fit them all on a single bookshelf). Basically, one uses general rules that compare stability. For example, a positively-charged carbon is more stable when it has more alkyl groups attached to it (the reason usually given for this is hyperconjugation). A carbon conjugated with a double bond is considered even more stable, due to resonance.



Regarding paper, paper is made of molecular fibres which are effectively infinitely long. To melt paper, one would have to disentangle these (as molecules need to be much farther apart and with much less attraction in liquid form), and even then one would be left with a very, very viscous liquid (which is not too different from a solid). So paper would be extremely hard to melt, if not impossible.