Really we don't need much for things like this, just about a RL week of decent RP toward this end, supporting journal entries and/or a confirming statement from a cleric of said deity.
If this is in regard to Rhynn being devoted to Lucinda, then that's something my own character has witnessed in-game so I don't really see a problem with this.
The proper proceedure is to make the request in Grievances and, once approved, ask a GM in-game to make the change for you.