Ruling on transgressing against the rights of kaafir workers
Question

                I stole 500 riyals from a man who was working for us, a shepherd who is not Muslim, after he developed a problem in his feet and was not able to walk. The money that I stole was the salary of this worker. I hope by Allah's grace that you can advise me what to do. I regret what I did to this poor worker. Please note that he has left and I do not know his address.
Praise be to Allah.
      Firstly: 

    One of the principles of good manners which is supported by 
    human nature and which Islam confirms is of great importance is rendering 
    back trusts and abhorrence of treachery and betrayal. Allah says 
    (interpretation of the meaning):

    “Verily, Allaah commands that you should render back the 
    trusts to those, to whom they are due; and that when you judge between men, 
    you judge with justice. Verily, how excellent is the teaching which He (Allaah) 
    gives you! Truly, Allaah is Ever All‑Hearer, All‑Seer”

    [al-Nisa’ 4:58]

    “O you who believe! Betray not Allaah and His Messenger, 
    nor betray knowingly your Amaanaat (things entrusted to you, and all the 
    duties which Allaah has ordained for you)”

    [al-Anfaal 6:27]. 

    On this site we have previously explained that it is haraam 
    to take the wealth of kaafirs by deceitful means. See the answer to question 
    number 50716. We have also 
    explained the obligation of returning stolen wealth to its kaafir owners. 
    See the answer to question 47086 
    and also 7545,
    14367 and
    31234. 

    Secondly: 

    Whoever falls into wrongdoing, robbery or consuming people's 
    wealth unlawfully then repents from that is obliged to return to each person 
    that which is rightfully his in this world 

    It was narrated that Abu Hurayrah (may Allah be pleased with 
    him) said: The Messenger of Allah (blessings and peace of Allah be upon him) 
    said: “Whoever has wronged his brother with regard to his honour or anything 
    else, let him seek his forgiveness today, before there will be no dinar and 
    no dirham [i.e., the Day of Resurrection], when if he has any good deeds (hasanaat), 
    some of his good deeds will be taken and given to the one who was wronged, 
    commensurate with the wrong that he did, and if he  does not have any good 
    deeds, some of the bad deeds (sayi’aat) of the one who was wronged will be 
    taken and thrown onto him.” Narrated by al-Bukhaari (2269). 

    And it was also narrated that Abu Hurayrah (may Allah be 
    pleased with him) said: The Messenger of Allah (blessings and peace of Allah 
    be upon him) said: “All rights will be restored on the Day of Resurrection, 
    until even the hornless sheep will settle its score with the one that has 
    horns.” Narrated by Muslim (4679). 

    But if the one who is in possession of the property does not 
    know who the rightful owner is or where he is, or he is unable to get it to 
    him, then he should give it in charity on his behalf, then if he gets in 
    touch with him the owner of the property or wealth is to be given the choice 
    between having the reward of the charity going to him or having his wealth 
    returned to him and the reward for it going to the one who gave it in 
    charity. 

    Shaykh al-Islam Ibn Taymiyah (may Allah have mercy on him) 
    said: 

    If he knows that his wealth includes permissible wealth and 
    haraam wealth but he does not know to whom it belongs, but he knows how much 
    it is, then he should divide the wealth according what is halaal and haraam 
    and take the halaal portion; the haraam portion should be given in charity 
    on behalf of its real owners, as should be done by one who possesses wealth 
    whose owners are unknown, such as money acquired by force, or things that 
    have been borrowed or entrust to him. The majority of scholars, such as 
    Maalik, Abu Haneefah, Ahmad ibn Hanbal and others said that he should give 
    it in charity. This is what is narrated in such cases from the Companions of 
    the Messenger of Allah (lessons and peace of Allah be upon him). If it is 
    not known how much is halaal and how much is haraam, then he should divide 
    the wealth in half, keeping half for himself and giving the other half to 
    its owners if he knows them, otherwise he should give it in charity. What he 
    gives in charity should be spent on the general interests of the Muslims: it 
    may be given to those who are entitled to zakaah, or spent on guests, or 
    used to help pilgrims go for Hajj, or be spent on jihad, or other charitable 
    causes that Allah and His Messenger love, as is done with all wealth whose 
    owners are unknown. This is what should be done by one who repents from 
    doing haraam things and has haraam wealth in his possession and does not 
    know who its owner is. End quote. Majmoo al-Fataawa (30/328) 

    See also: Majmoo’ al-Fataawa 28/592 ff. 

    Shaykh Mustafa al-Ruhaybaani (may Allah have mercy on him) 
    said: 

    He has to give it in charity (when there is no trustworthy 
    ruler), as is the case nowadays. But if there is a trustworthy ruler, which 
    is more rare than red sulphur, then in that case he does not have to give it 
    in charity; rather he has the choice between giving it to him [the ruler], 
    so that he will no longer be responsible for it, or giving it in charity. 
    That is a sound view, provided that he takes responsibility for it before 
    the owners if he finds them, because giving it in charity without assuming 
    responsibility for it is a waste of the owner’s property. The is the ruling 
    concerning stolen property and the like, such as lost property that he 
    should not have picked up and he did no announce; in that case he may give 
    it in charity on behalf of its owner, provided that he will still take 
    responsibility for it before its owner.  

    Mataalib Ooli al-Nuha, 4/66 

    And Allah knows best.