Things that proficiency bonus increases:

 1. Saves a character is proficient in  
 2. Attacks with weapons a character is proficient in  
 3. Ability checks made with skills or tools a character is proficient in  
 4. Bards and Fighters have ways of adding half their proficiency bonus to untrained ability checks  
 5. Bards and rogues (and some feats) can add double proficiency bonus to some checks  

### How can we simulate this with existing magic items?  

 - A Stone of Good Luck (uncommon, attunement) gives +1 to all ability checks and saving throws.  This is better than a +1 to points 1, 3 and 4  
 - A +1 Weapon (uncommon) gives +1 to attack rolls with it.  This is worse than point 2 in general, but for a character who only uses 1 weapon it's not much of a difference   

An item that gave +1 to proficiency bonus would probably have to be at least Rare, given that it combines the properties of two uncommon items (and allows for the use of a separate weapon), but I don't see it breaking anything.  In a few cases it will add two points to a skill (point 5); this is nothing to be sniffed at, but if the item you're crafting is meant to be Legendary, you're still well within bounds of that.  

### Spellcasters and proficiency boosts

Spellcasters with a +1 to proficiency get a +1 to their attack rolls and to their save DCs.  Increased save DC is a surprisingly [thorny issue][1], but in the worst case (though I'd argue that it's not really any worse than a +1 to hit) we can simulate it with a Very Rare item.   Unless you're regularly casting with two different stats, the +1 from a stat-increasing tome is much better than this, since it applies to some ability checks and saving throws also, and is not losable.   

### Is it overpowered? No.  

Our final item is generally worse than a Very Rare and two Uncommons (you're unlikely to be making full use of both the weapon boost and the spell boost), which makes it hard to argue that it's overpowered as a Legendary.  


  [1]: https://rpg.stackexchange.com/questions/101667/is-an-item-increasing-spell-save-dc-balanced