Sachverhalt:
A. Im Januar 2007 reichte die Swisscom Mobile AG (heute: Swisscom (Schweiz) AG; im Folgenden: Swisscom) ein Baugesuch ein, um ihre bestehende Mobilfunkanlage auf dem 14-geschossigen Hochhaus Grossmatt 1 in Kappel mit UMTS zu erweitern. Gleichzeitig stellte auch die Kantonspolizei Solothurn ein Gesuch um Erweiterung der bestehenden Kommunikationsanlage mit Polycom- und Richtfunkantennen; dieses Gesuch wurde jedoch am 5. Oktober 2007 zurückgezogen.
Auf dem Dach des Hochhauses Grossmatt 1 befindet sich bereits eine Telepage-Anlage der Swissphone Wireless AG.
Gegen das Bauvorhaben gingen zahlreiche Einsprachen ein, darunter auch der Einwohnergemeinde Kappel und der Eheleute X._. Am 20. August 2007 wies die Baukommission Kappel die Einsprachen ab und erteilte die Baubewilligung.
B. Dagegen erhoben sowohl die Eheleute X._ als auch die Einwohnergemeinde Kappel Beschwerde an das Bau- und Justizdepartement des Kantons Solothurn. Dieses wies die Beschwerden am 19. Februar 2008 ab.
C. Gegen den Departementsentscheid gelangten die Eheleute X._ mit Beschwerde an das Verwaltungsgericht des Kantons Solothurn. Auch die Einwohnergemeinde Kappel erhob Beschwerde, zog diese aber am 20. März 2008 zurück.
Am 27. November 2008 wies das Verwaltungsgericht die Beschwerde ab. Es hielt im Dispositiv fest, dass die Anlage der Swisscom spätestens im Zeitpunkt der Inbetriebnahme in das Qualitätssicherungssystem der Swisscom zu integrieren sei.
D. Am 26. Januar 2009 haben die Eheleute X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen die Aufhebung des angefochtenen Entscheids und der vorinstanzlichen Entscheide sowie die Abweisung des Baugesuchs. Ferner sei die Strahlenbelastung des bestehenden Telepage-Funkdiensts der Swissphone Wireless AG zu messen und diese Anlage sei an den Standort Gunzgen zu verschieben, an den bereits die KAPO Solothurn ihren Funkdienst im laufenden Verfahren verschoben hat. Eventuell sei die Streitsache an das Verwaltungsgericht zurückzuweisen.
E. Die Baukommission Kappel, das Verwaltungsgericht sowie das Bau- und Justizdepartement schliessen auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Die Einwohnergemeinde Kappel hat auf eine Vernehmlassung verzichtet, verweist aber auf ihre seinerzeitige Beschwerde vom 29. Februar 2009. Die Swisscom verweist ihrerseits auf die Entscheide der Vorinstanzen, insbesondere des Verwaltungsgerichts.
F. Das Bundesamt für Umwelt (BAFU) vertritt in seiner Vernehmlassung die Auffassung, das Verwaltungsgericht habe die Badezimmer im obersten Stock des Standortgebäudes zu Unrecht nicht als Orte mit empfindlicher Nutzung (OMEN) i.S.v. Art. 3 Abs. 3 lit. a der Verordnung vom 23. Dezember 1999 über den Schutz vor nichtionisierender Strahlung (NISV; SR 814.710) anerkannt. Es seien zusätzliche Sachverhaltsabklärungen erforderlich, um festzustellen, ob der Anlagegrenzwert an diesen Orten eingehalten werde. Den Beteiligten wurde Gelegenheit gegeben, hierzu Stellung zu nehmen.
G. Mit Verfügung vom 26. Februar 2009 wurde der Beschwerde die aufschiebende Wirkung in dem Sinne erteilt, dass die neuen Mobilfunkantennen während der Dauer des bundesgerichtlichen Verfahrens nicht in Betrieb genommen werden dürfen.

Erwägungen:
1. Gegen den kantonal letztinstanzlichen Entscheid des Verwaltungsgerichts steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (<ref-law>). Die Beschwerdeführer sind als Nachbarn der streitigen Mobilfunkanlage grundsätzlich zur Beschwerde legitimiert (<ref-law>). Da auch die übrigen Sachurteilsvoraussetzungen vorliegen, ist auf die Beschwerde (vorbehältlich zulässiger und begründeter Rügen) einzutreten.
2. Die Beschwerdeführer rügen zunächst, das Verwaltungsgericht sei auf ihre Anträge betreffend die Telepage-Anlage der Swissphone Wireless AG zu Unrecht nicht eingetreten.
2.1 Das Verwaltungsgericht ging davon aus, dass diese Anlage nicht Gegenstand des Baugesuchsverfahrens und deshalb nicht Streitgegenstand sei.
2.2 Die Beschwerdeführer bestreiten dies. Sie weisen darauf hin, dass die Swisscom auch ein Standortdatenblatt zur Telepage-Anlage eingereicht habe; auch dieses sei Gegenstand der öffentlichen Auflage gewesen. Die drei Anlagen (der Swisscom, der Kantonspolizei Solothurn und der Swissphone Wireless AG) bildeten eine Einheit, deren Inhaberin die Swisscom sei.
2.3 Es trifft zu, dass die Swisscom als "site manager" auch ein Standortdatenblatt für Rundfunk und Funkrufsendeanlagen betreffend die bereits bestehende Telepage-Anlage eingereicht hat, als deren Netzbetreiberin die Swissphone Telecom AG und als Veranstalterin die Swissphone Wireless AG genannt werden. Das Standortdatenblatt enthält den Vermerk "ersetzt das Standortdatenblatt vom 19. Oktober 2001".
Allerdings ist unstreitig, dass die Telepage-Einrichtung der Swissphone Wireless AG weder geändert noch erweitert werden sollen: Das Baugesuch betraf ausschliesslich die Erweiterung der bestehenden Sendeanlage der Swisscom mit UMTS sowie (ursprünglich) mit Polycom- und Richtfunkantennen der Kantonspolizei.
2.4 Entgegen der Auffassung der Beschwerdeführer bildet die Telepage-Einrichtung auch keine rechtliche Einheit mit der Mobilfunkanlage der Swisscom:
Anh. 1 der NISV unterscheidet zwischen Sendeanlagen für Mobilfunk und drahtlosen Teilnehmeranschlüssen einerseits (Ziff. 6) und Sendeanlagen für Rundfunk und übrige Funkanwendungen andererseits (Ziff. 7); zu letzteren gehört die streitige Telepage-Anlage.
Gemäss Ziff. 62 Abs. 1 Anh. 1 NISV zählen zu einer Mobilfunkanlage alle Sendeantennen für die Funkdienste nach Ziffer 61, die auf demselben Mast angebracht sind oder die in einem engen räumlichen Zusammenhang, namentlich auf dem Dach des gleichen Gebäudes, stehen. Die gleiche Definition findet sich in Ziff. 72 Abs. 1 Anh. 1 NISV für alle Sendeantennen für Funkanwendungen nach Ziffer 71, die auf demselben Mast angebracht sind oder die in einem engen räumlichen Zusammenhang stehen: Diese bilden gemeinsam eine Anlage. Nicht zu einer gemeinsamen Anlage gehören dagegen Sendeantennen für Mobilfunk einerseits und für Rundfunk bzw. übrige Funkanwendungen andererseits, auch wenn sie - wie im vorliegenden Fall - auf demselben Dach oder sogar am selben Mast angebracht sind. Sie müssen daher - wie das BAFU in seiner Vernehmlassung bestätigt - jede für sich den jeweils einschlägigen Anlagegrenzwert einhalten.
2.5 Insofern diente das im Baubewilligungsverfahren ausgefüllte Standortdatenblatt für die Telepage-Anlage lediglich der Information und bewirkte keine Änderung dieser Anlage. Geändert wurde vielmehr die - im Standortdatenblatt für Rundfunk und Funkrufsendungen in Zusatzblatt 4 Tabelle 2 als "weitere Sendeanlage" aufgeführte - Mobilfunksendeanlage der Swisscom. Das Verwaltungsgericht ging daher zu Recht davon aus, dass die Telepage-Anlage nicht Gegenstand des streitigen Baugesuchsverfahrens war.
Soweit die Beschwerdeführer Zweifel an der Bewilligung oder am rechtmässigen Betrieb der Telepage-Anlage haben, müssen sie dies gegenüber der Swissphone Wireless AG bzw. der Swissphone Telecom AG geltend machen bzw. sich erstinstanzlich an die zuständigen kommunalen oder kantonalen Vollzugsbehörden (Baubehörde bzw. NIS-Fachstelle) wenden.
2.6 Nach dem Gesagten kann auch im bundesgerichtlichen Verfahren nicht auf die Rügen und Anträge betreffend die Telepage-Anlage eingetreten werden.
3. Die Beschwerdeführer machen weiter geltend, der Anlagegrenzwert für Mobilfunksendeanlagen von 5 V/m (Ziff. 64 lit. c Anh. 1 NISV) sei im obersten Geschoss des Standortgebäudes im Bereich der Lüftungsschächte nicht eingehalten.
3.1 Das Verwaltungsgericht hielt fest, dass die Decke des Hochhauses aus 20 cm armiertem Beton bestehe. Die zwei Lüftungsschächte befänden sich jeweils über zwei angrenzenden Bädern. Ein Badezimmer sei kein Ort mit empfindlicher Nutzung (OMEN), an dem der Anlagegrenzwert einzuhalten sei. Als solche gälten bloss Räume in Gebäuden, in denen sich Personen regelmässig während längerer Zeit aufhalten (<ref-law>). Dazu gehörten nur eigentliche Wohn-, Schlaf- und Arbeitsräume, in denen sich Personen während mindestens 800 Stunden pro Jahr aufhalten (mit Hinweis auf Benjamin Wittwer, Bewilligung von Mobilfunkanlagen, Diss. Zürich 2006, S. 81).
3.2 Das BAFU hält für die Frage, wann ein längerer Aufenthalt i.S.v. <ref-law> vorliege, zwei Gesichtspunkte für wegleitend: Einerseits müsse aufgrund der klaren materiell-rechtlichen Differenz zwischen den Anforderungen der NISV an die Emissionsbegrenzungen bei OMEN und bei Orten für den kurzfristigen Aufenthalt (OKA) auch die massgebende Aufenthaltsdauer bei OMEN deutlich von derjenigen bei OKA abgegrenzt werden; andererseits lasse sich aus der Tatsache, dass die vorsorglichen Anforderungen von Anh. 1 NISV bei bestimmten Funkanwendungen und bei Radaranlagen erst gelten, wenn eine Anlage während mindestens 800 Stunden pro Jahr am gleichen Standort sendet, das Indiz ableiten, dass der Verordnungsgeber eine relevante, länger dauernde Belastung durch Hochfrequenzstrahlung erst ab einer Grössenordnung von 800 Stunden jährlich annehmen wollte.
Demnach könnten Orte tendenziell als empfindlich gelten, wo sich Menschen während jährlich mindestens 800 Stunden aufhalten, was einer täglichen Aufenthaltsdauer von ca. 2 Stunden entspreche. Da es erheblichen Aufwand erfordere, im Einzelfall zu ermitteln, wie welche Räume in Gebäuden konkret genutzt werden, sei dem Grundsatz der Prozessökonomie und der Praktikabilität folgend die Bestimmung der OMEN zu generalisieren: Es müsse sich um Räume in Gebäuden handeln, in denen sich Menschen bei der bestimmungsgemässen Nutzung während 800 Stunden pro Jahr oder rund zwei Stunden täglich aufhalten können (Urs Walker, Verordnung über den Schutz vor nichtionisierender Strahlung (NISV): Die aktuellen Rechtsfragen, URP 2003 S. 110 f.; Vollzugsempfehlung zur NISV "Mobilfunk und WLL-Basisstationen" S. 14 ff.; Benjamin Wittwer, a.a.O., S. 81 a.E.).
Nach Auffassung des BAFU gehören dazu nicht nur eigentliche Wohn-, Schlaf- und Arbeitsräume, sondern auch Badezimmer: Einerseits sei zumindest in Badezimmern von Mehrpersonenhaushalten eine jährliche Aufenthaltsdauer von 800 Stunden sehr wahrscheinlich, ohne dass ensthaft bestimmte Aufenthaltsdauern einzelnen Personen zugerechnet werden könnten; und andererseits seien Badezimmer heute nicht selten als "Wellness-Oasen" mit teils fliessenden Übergängen zu anderen Wohnräumen konzipiert.
3.3 Diese Auslegung von <ref-law> überzeugt. Handelt es sich somit bei den Badezimmern im obersten Geschoss des Standortgebäudes um OMEN, so muss auch dort der Anlagegrenzwert eingehalten werden. Ob dies der Fall ist, wurde vom Verwaltungsgericht nicht geprüft und lässt sich auch nicht ohne Weiteres den Akten entnehmen (vgl. dazu die Hinweise des BAFU, Vernehmlassung Ziff. 3.2).
3.4 Das Bau- und Justizdepartement hat am 20. Mai 2009 mitgeteilt, das Amt für Umwelt bestätige, aufgrund genauer Abklärungen vor Ort, dass die Lüftungsschächte eine Gebäudedämpfung von mindestens 15 dB aufweisen, weshalb der Anlagegrenzwert auch in den Badezimmern eingehalten werde.
Die Beschwerdeführer bestreiten dies und rügen zudem eine Verletzung des rechtlichen Gehörs, sofern das Amt für Umwelt zur Abklärung einen Augenschein ohne Beteiligung der Parteien vorgenommen habe.
Ist somit der Sachverhalt noch streitig, rechtfertigt es sich, die Sache zur ergänzenden Sachverhaltsermittlung und neuer Beurteilung an das Verwaltungsgericht zurückzuweisen.
4. Dies führt zur teilweisen Gutheissung der Beschwerde, soweit darauf einzutreten ist. Nachdem das Verwaltungsgericht ohnehin nochmals über die Gerichtskosten entscheiden muss, werden die diesbezüglichen Rügen der Beschwerdeführer gegenstandslos.
Bei diesem Ausgang des Verfahrens rechtfertigt es sich, die Gerichtskosten der privaten Beschwerdegegnerin aufzuerlegen und keine Parteientschädigungen zuzusprechen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen und der Entscheid des Verwaltungsgerichts des Kantons Solothurn vom 27. November 2008 wird aufgehoben. Die Sache wird zur Sachverhaltsergänzung und zu neuer Beurteilung an das Verwaltungsgericht zurückgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden der Swisscom (Schweiz) AG auferlegt.
3. Es werden keine Parteientschädigungen zugesprochen.
4. Dieses Urteil wird den Parteien, der Einwohnergemeinde Kappel, dem Bau- und Justizdepartement sowie dem Verwaltungsgericht des Kantons Solothurn und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 19. Juni 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Gerber