Taking into account spins, we classify all two-body non-relativistic Dark Matter annihilation channels to the allowed polarization states of Standard Model particles, computing the energy spectra of the stable final-state particles relevant for indirect DM detection. We study the DM masses, annihilation channels and cross sections that can reproduce the PAMELA preliminary indications of an e+ excess consistently with the PAMELA p-bar data and the ATIC/PPB-BETS e++e- data. From the PAMELA data alone, two solutions emerge: (i) either the DM particles that annihilate into W,Z,h must be heavier than about 10 TeV or (ii) the DM must annihilate only into leptons. Thus in both cases a DM particle compatible with the PAMELA excess seems to have quite unexpected properties. The solution (ii) implies a peak in the e++e- energy spectrum, which, indeed, seems to appear in the ATIC/PPB-BETS data around 700 GeV. If upcoming data from ATIC-4 and GLAST confirm this feature, this would point to a O(1) TeV DM annihilating only into leptons. Otherwise the solution (i) would be favored. We comment on the implications of these results for DM models, direct DM detection and colliders as well as on the possibility of an astrophysical origin of the excess.