加盟店側からユーザーとPayPayの連携を解除することはできますか？

はい、可能です。 ドキュメントに記載されているUnlink user（https://api.paypay.ne.jp/v2/user/authorizations/{userAuthorizationId}）をご利用ください。