To change the address of a Company it can be classified into three categories 1. Within same state 2. Within same state but outside the jurisdiction of Roc 3. From state to another If Within state file Inc-22 attachment latest electricity bill, rent agreement and noc if rented premises. If Change is from one Roc to another, then file Inc-23 with RD and public notice in newspaper. And If change from one state to another requires approval of Central Govt Pass Special Resolution, file MGT-14, Publish advertisement, file Inc-23, Inc-28 with Roc and then Inc-22 , Roc will issue a fresh Certificate of Incorporation.
Fees you can check by enquire fees at Mca by filling the CIN of the Company for requisite forms and the form can be signed by One director and certified by CA/CS/CMA in Practice.
If it's inter city than its easy if it's intra state one city to another in same city than bit lengthy process but simple if its inter state it's a long process.