Can a single co-authored paper be part of two stapled dissertations (by two people)?
Every university should have guidelines around how publications can be incorporated into a PhD thesis. The correct advice (as @Andreas notes) is to consult these guidelines. Furthermore, it seems that PhD by publication is becoming more popular and guidelines are evolving.

I'm familiar with various models of "PhD by publication". At my institution in Australia, the PhD student is expected to be first author on any major publication that forms part of a PhD by publication submission. They also need to attach a form for each publication outlining their contribution and the contribution of the other authors. The form needs to be signed by the other authors. Non-first-author publications can be included but they are intended more as supplementary contributions. Exactly what this means is a little open to interpretation.

By way of a concrete example, here is an example of such a policy (the policy at your university may differ):


  It is expected that the student will be the first author on the papers, as per 1 above; the number of co-authors is limitless. Students may be second or later authors on additional papers.


Thus, to answer your specific question, at my institution, a paper could be included in more than one PhD. However, the student who is first author would have a stronger inherent case for it being seen as an integral part of their thesis. Furthermore, the contributions of all authors would have to be explained. 

You may want to consider practical alternatives such as thinking about how the work could form two papers where you each drive one paper as reflected in being first-author on that paper.