Fascinating question. I cannot analyze it as well as a pedantic grammarian, but I believe I can illuminate the issue.
Because I am unsure that "together with" is technically a conjunction, I will purposely avoid using that word. Instead I will say that the phrase "connects" some parts of the sentence together.
I think the question is: what does "together with" connect?
My work ethic together with belief in my ability has led to progress.
To rephrase your question, you astutely ponder if "together with" connects "My" and "belief in my ability." If the answer is yes, then the sentence is "correct". I typically dislike the idea of "correct" grammar in English, so I prefer to aim for other things such as reducing ambiguity or distracting the reader with awkward phrasing.
I agree with you that if "and" were substituted for "together with" then your sentence would flow nicely and your meaning would be clear: you have two qualities that (you imply worked together and) caused progress.
"Together with" is not one of the FANBOYS, so the sentence does not flow as well if you has used "and." This might be strictly a convention issue: we readers are not accustomed to the sentence construction you used, so the novelty arrested our attention.
However, it might be that "together with" is connecting two things you did not intended to connect. My intuition tells me that "together with" is connecting "work ethic" (without the word "My") to "belief in my ability." If that is what is happening, either by the "rules" of grammar or by the writing conventions of our times, then the sentence is awkward and potentially confusing.
Another perspective: what if we added commas to offset the dependent clause?
My work ethic, together with belief in my ability, has led to progress.
To my eye, the above sentence is awkward because it is missing "my".
My work ethic, together with my belief in my ability, has led to progress.
What about the word, "and?"
My work ethic, and belief in my ability, has led to progress.
My work ethic, and my belief in my ability, has led to progress.
Again, I feel there is a qualitative difference between "and" and "together with", but I cannot use the pedantic terms to describe the differences, if there are in fact any technical differences between the two terms.
Nevertheless, convention is often stronger than "rules". Consider the dying use of the subjunctive "were" in favor of the more convenient "was," and the all but dead and buried "whom" in favor of "who." Therefore, if your goal is powerful, clear writing, then convention alone is enough of a reason to repeat the subject, "my", before "belief in my ability."