I know this is a pretty old post but I would like to provide some up-to-date information about this in case anyone else comes across this and needs their PUK code.
You can actually find your PUK code when logged in to your My Account profile on Fido.ca. You can find this under the My Fido Service column on the left hand side of the page, next to the Your Phone section. Simply click the Retrieve your PUK Code link, select your phone number if you have multiple lines in the account, and press submit.
Hope this helps!