• Checking in with any churches they cross paths with and helping them with small menial tasks as long as that church isn't dedicated to something their faith stands steadfastly against - such as clearing out an infestation of some menial-to-a-PC-but-not-to-commoners pest or other in the basement/nearby fields/woods/etc, giving a few hours of time to help with physical labor such as carrying in lumber for a repair/addition job, newly-made/arrived pews/furniture, etc.
• Finding those of the same faith and giving them blessings (which may or may not need to have any real mechanical effect).
• Leaving small altars/items of the faith throughout the world - in shops where allowed, in public places, in places where no one might find them but if someone did stumble upon it they might find it as a sign (such as deep in the woods tucked in a lonely/strange tree, by the top of a waterfall, or anywhere else; even better if they aren't given specifics of where but are told to "keep your eyes open for lonely places where lost souls might seek answers... those places.").
• Collecting something small but relevant to the faith, and leaving those as offerings in places of worship (specifically colored stones, plants, flowers, feathers, anything).
• A nonlinear pilgrimage with a list of places, which should conveniently happen to include places at or nearby where the PCs will be visiting anyway, as well as a couple or few that are out of the way - with adventures or mini-quests awaiting at the out-of-the-way places, such as "a grove once sacred to me, recently ravaged by the undead... clear this place, and revitalize it in my honor" or "craft an altar in x part of the world, where my radiance has yet reach" or perhaps they find a priest/cleric at one of these areas and they need help with something.
• Recreating an ancient relic to the deity by collecting the pieces (smaller than recovering holy relics, but bigger grand-scheme as it's creating a holy relic), such as a sword (collect the raw materials, find a special enchanter whom also happens to be of the faith whom also happens to be in a certain part of the world where a special type of magic resides, a smith of the faith able to forge the materials maybe who is even willing to travel to prior-mentioned specific part of the world in order to do so, etc), a book (the pages of which were torn out by someone once of the faith but now corrupt; most were collected by priests who are now in different churches across the world but still need to track down the corrupt one to finish the job; pairs well with pilgrimage), etc.
• Being in a certain place at/by a certain time in order to participate in some local folk holiday or ritual dedicated to the deity; bonus points for extra adventure once there (ie rescue someone captured by local bandits who is needed to perform the ritual; something interrupts the ritual and needs to be handled, maybe even both, etc) or on the way (need to bring a McGuffin from somewhere else to that place for the ritual).

Hello The MindMaster

How about having a nearby temple being overrun and destroyed by enemies of the faith/ beasts/ bandits / monsters 

and your paladin now has to go in a series of quests of rebuild it. 

1) free it from the grasps of the enemies- dungeon encounter
2) get it new supplies to start rebuilding - escort caravan mission 
3) find new priests to run the temple and noble lords to fund it  - political- roleplaying quest 

 

A few more ideas:

  * Officiating at an important wedding b/c the usual cleric is dead/sick.  

  * Protecting a herd of animals for a certain # of days and nights b/c they are considered sacred to the religion and something has been mysteriously killing them

  * Finding out who as been leaving blasphemous literature about the faith on the doorsteps of the locals. 

  * Gathering a particular difficult-to-find flower or branch that happens to be in monster territory or is inside the exclusive floral collection of a particularly cantankerous noble.

.