结论：公司是否有责任，取决于劳务派遣协议的具体内容、公司解除用工关系的合法性以及是否给劳动者造成损害等多个因素。以下从不同角度进行分析：
一、劳务派遣协议的角度
协议内容：劳务派遣协议是劳务派遣单位（即劳务公司）与用工单位（即公司）之间签订的，用于明确双方权利和义务的协议。如果协议中明确规定了用工期限、解除条件等，且公司解除用工关系的行为符合协议约定，那么公司可能无需承担额外责任。
协议履行：如果劳务派遣协议中未明确规定用工期限或解除条件，或者公司解除用工关系的行为违反了协议约定，那么公司可能需要承担违约责任，包括赔偿劳务公司因此遭受的损失，以及可能涉及对劳动者的赔偿（如果劳务公司因此无法履行对劳动者的义务）。
二、劳动法的角度
合法解除：根据《中华人民共和国劳动合同法》的相关规定，用工单位可以在符合法定条件的情况下解除与劳动者的用工关系，如劳动者严重违反用工单位规章制度、不能胜任工作等。如果公司解除用工关系的行为符合这些法定条件，且程序合法，那么公司无需承担额外责任。
违法解除：如果公司解除用工关系的行为违反了劳动法的规定，如无正当理由解除、未提前通知等，那么公司可能需要承担违法解除的法律责任，包括支付经济补偿金或赔偿金给劳动者。在这种情况下，虽然直接的法律责任可能由劳务公司承担（因为劳动者是与劳务公司签订的劳动合同），但公司可能因违法用工而面临劳务公司的追偿或行政处罚。
三、损害赔偿的角度
劳动者损害：如果公司解除用工关系的行为给劳动者造成了损害（如失业、收入减少等），且这种损害是由于公司的违法行为或过错造成的，那么劳动者有权要求公司承担赔偿责任。在这种情况下，劳务公司可能作为劳动者的雇主，先向劳动者支付赔偿，然后再向公司追偿。
劳务公司损害：如果公司解除用工关系的行为导致劳务公司遭受了损失（如无法履行与其他客户的合同、声誉受损等），那么劳务公司有权要求公司承担赔偿责任。
建议
审查劳务派遣协议：公司应首先审查与劳务公司签订的劳务派遣协议，明确双方的权利和义务，以及解除用工关系的条件和程序。
遵守劳动法规定：公司在解除用工关系时，应确保行为符合劳动法的规定，避免违法解除带来的法律责任。
积极沟通协商：如果公司确实需要解除用工关系，应与劳务公司和劳动者进行积极沟通协商，尽量达成一致意见，减少纠纷和损失。
寻求法律帮助：如果公司在处理劳务派遣关系时遇到法律问题或纠纷，应及时寻求专业律师的法律帮助，以确保自身权益得到保护。
如有任何进一步的问题或需要更具体的法律建议，请直接向我咨询。